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$.

Now we can formulate the second part of the algorithm.

Berlekamp's algorithm (second part).

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".

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".

**Compute $x^{qi} \mathrm{rem} f$ for $i=0,...,n-1$**__Step 1.__**Form matrix $Q$ using the result of Step 1**__Step 2.__**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 3.__**Choose arbitrary element $a = c_1 b_1 + ... + c_r b_r, c_i \in F_q$**__Step 4.__**$g_1 = \gcd(a,f)$. If $g_1 \neq 1$**__Step 5.__**return**$g_1$.**$g_2 = \gcd(a^{(q-1)/2} \mathrm{rem} f - 1, f)$. If $g_2 \neq 1, g_2 \neq f$**__Step 6.__**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