Berlekamp

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.

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.