Yesterday I finished porting Berlekamp's algorithm from nmod_poly module to fmpz_mod_poly_factor module.
Unlike Cantor-Zassenhaus and Kaltofen-Shoup algorithms this algorithm uses linear algebra -- not number theory. Berlekamp algorithm consists of two parts. The first part is standard: squarefree factorization. The second part is more specific.
Assume for simplicity that q is an odd prime number. $R = F_q[x]/<f>$ is a vector space of dimension $n = \deg f$ over $F_q$. Let $\beta : R \to R$ be a mapping: $\beta(a) = a^q-a$. Consider the kernel of $\beta$. If $f$ = $f_1$ ... $f_r$ where $f_i$ is irreducible $\forall i$, then for $a \in F_q[x]$ we have
$$a \mod f \in \ker \beta \Leftrightarrow a^q \equiv a \mod f \Leftrightarrow a^q \equiv a \mod f_i \,\,\, \forall i$$
(by Fermat's little theorem)
Thus $\ker \beta = F_q \times ... \times F_q = F_q^r$. $a \mod f \in \ker \beta \Leftrightarrow (a \mod f_1, ... , a \mod f_r) = (a_1 \mod f_1, ... , a_r \mod f_r)$ for some $a_i \in F_q$ Denote by $Q$ the matrix representing the Frobenius map $S: S(a) = a^q$ with respect to the polynomial basis $x^{n-1} \mod f, ... , x \mod f, 1 \mod f$ of $R$.
Fact. $f$ is irreducible $\Leftrightarrow r = 1 \Leftrightarrow \mathrm{rank}(Q-I) = n-1$
Now we can formulate the second part of the algorithm.
Berlekamp's algorithm (second part).
Input and Output.
On input we have a monic squarefree polynomial $f\in F_q[x]$ of degree $n$.
On output we get an irreducible divisor of $f$ or "failure".
Step 1. Compute $x^{qi} \mathrm{rem} f$ for $i=0,...,n-1$
Step 2. Form matrix $Q$ using the result of Step 1
Step 3. Compute rank of $(Q-I)$ and basis $b_1, ... , b_r$ of $\ker \beta$ (e.g. using Gaussian elimination for $Q-I$). If $\mathrm{rank} = n-1$ return $f$.
Step 4. Choose arbitrary element $a = c_1 b_1 + ... + c_r b_r, c_i \in F_q$
Step 5. $g_1 = \gcd(a,f)$. If $g_1 \neq 1$ return $g_1$.
Step 6. $g_2 = \gcd(a^{(q-1)/2} \mathrm{rem} f - 1, f)$. If $g_2 \neq 1, g_2 \neq f$ return $g_2$, else return "failure"
To get the full variant of factorization algorithm one has to call the second part many times until f is irreducible.
Unlike Cantor-Zassenhaus and Kaltofen-Shoup algorithms this algorithm uses linear algebra -- not number theory. Berlekamp algorithm consists of two parts. The first part is standard: squarefree factorization. The second part is more specific.
Assume for simplicity that q is an odd prime number. $R = F_q[x]/<f>$ is a vector space of dimension $n = \deg f$ over $F_q$. Let $\beta : R \to R$ be a mapping: $\beta(a) = a^q-a$. Consider the kernel of $\beta$. If $f$ = $f_1$ ... $f_r$ where $f_i$ is irreducible $\forall i$, then for $a \in F_q[x]$ we have
$$a \mod f \in \ker \beta \Leftrightarrow a^q \equiv a \mod f \Leftrightarrow a^q \equiv a \mod f_i \,\,\, \forall i$$
(by Fermat's little theorem)
Thus $\ker \beta = F_q \times ... \times F_q = F_q^r$. $a \mod f \in \ker \beta \Leftrightarrow (a \mod f_1, ... , a \mod f_r) = (a_1 \mod f_1, ... , a_r \mod f_r)$ for some $a_i \in F_q$ Denote by $Q$ the matrix representing the Frobenius map $S: S(a) = a^q$ with respect to the polynomial basis $x^{n-1} \mod f, ... , x \mod f, 1 \mod f$ of $R$.
Fact. $f$ is irreducible $\Leftrightarrow r = 1 \Leftrightarrow \mathrm{rank}(Q-I) = n-1$
Now we can formulate the second part of the algorithm.
Berlekamp's algorithm (second part).
Input and Output.
On input we have a monic squarefree polynomial $f\in F_q[x]$ of degree $n$.
On output we get an irreducible divisor of $f$ or "failure".
Step 1. Compute $x^{qi} \mathrm{rem} f$ for $i=0,...,n-1$
Step 2. Form matrix $Q$ using the result of Step 1
Step 3. Compute rank of $(Q-I)$ and basis $b_1, ... , b_r$ of $\ker \beta$ (e.g. using Gaussian elimination for $Q-I$). If $\mathrm{rank} = n-1$ return $f$.
Step 4. Choose arbitrary element $a = c_1 b_1 + ... + c_r b_r, c_i \in F_q$
Step 5. $g_1 = \gcd(a,f)$. If $g_1 \neq 1$ return $g_1$.
Step 6. $g_2 = \gcd(a^{(q-1)/2} \mathrm{rem} f - 1, f)$. If $g_2 \neq 1, g_2 \neq f$ return $g_2$, else return "failure"
To get the full variant of factorization algorithm one has to call the second part many times until f is irreducible.
I also made Kaltofen-Shoup algorithm to use Brent-Kung algorithm for modular composition. I measured working time of Cantor-Zassenhaus, Kaltofen-Shoup and Berlekamp algorithms in the simplest case when an input polynomial has 1..6 factors of degree 1..8 and multiplicity 1..31. On each iteration (one iteration is a complete factorization of one polynomial) all parameters of input polynomial are randomly chosen (with uniform distribution). There is a table describing results on my computer (NI $-$ number of iterations, CZ $-$ Cantor-Zassenhaus, B $-$ Berlekamp, KS $-$ Kaltofen-Shoup):
NI : 100 200 300 400 500 600 700 800 900 1000
CZ time (sec) : 10.71 18.98 27.20 35.53 46.02 55.36 64.10 72.11 82.54 91.79
B time (sec) : 1.65 2.98 4.34 6.65 8.36 9.79 11.44 12.92 14.53 15.91
KS time (sec) : 1.55 2.92 4.09 5.80 7.23 8.56 10.06 11.56 12.91 14.13
Of course it's necessary to make more tests because algorithm effectiveness can depend on some special properties of input polynomials or on field characteristic.
just a remark - one can make TeX much more readable on blogspot:
ReplyDeletehttp://tex.stackexchange.com/questions/13865/how-to-use-latex-on-blogspot
Thanks a lot! Now it looks better:-)
DeleteOh wow! Your explanations on Berelekamp, Cantor-Zassenhaus, and Kaltofen-Shoup are very helpful for understanding what they are doing. KS is new to me but I have seen B and CZ in coding theory many times but have never understood how they work (I just accepted them as "magic"). Thanks!
ReplyDelete