Irreducibility testing

Fact. A polynomial $f\in F_q[x]$ of degree $n\geq 1$ is irreducible if and only if
1) $x^{q^n}\equiv x \mod f$ and
2) $\gcd (x^{q^{n/t}}-x, f)=1$ for all prime divisors $t$ of $n$.

From this fact one can get the Rabin's irreducibility test:

Irreducibility test (Rabin)
Input and Output  On input we have $f\in F_q[x]$ of degree $n$. On output test gives an answer "reducible" or "irreducible".
Step 1.  Compute $a=x^{q^n} \mathrm{rem} f$. If $a\neq x$ return "reducible".
Step 2. Find prime divisors of $n$.
Step 3. For all prime divisors $t$ of $n$ compute $b=x^{q^{n/t}} \mathrm{rem} f$. If $\gcd(b-x, f)\neq 1$ return "reducible".
Step 4. Return "irreducible".

Another possibility is to use distinct-degree factorisation to test irreducibility.

Irreducubility test (ddf)
Step 1.  Check if $f$ is squarefree (by computing it's derivative). If not, return "reducible".
Step 2. Build ddf $f^{[1]},...,f^{[n]}$ for $f$.
Step 3. If $\deg f^{[n]}=n$ return "irreducible", else return "reducible".

Since fmpz_mod_poly doesn't have fast gcd computation and fast modular composition implemented, the ddf-based algorithm turns out to be faster for it.

Making factor_equal_deg_prob to work for q=2

In my previous posts I described the variant of equal-degree splitting for odd prime powers. This algorithm requires some modification for fields with characteristic 2.

For $m\in \mathbb{N}$ define the $m$th trace polynomial over $F_2$ by $T_m=x^{2^{m-1}}+x^{2^{m-2}}+...+x^2+x.$  Let $q = 2^k$ for some $k\in \mathbb{N}$, $f\in F_q[x]$ squarefree of degree $n$, with $r\geq 2$ irreducible factors $f_1,...,f_r\in F_q[x], R=F_q[x]/<f>$

This modification exploits two facts:

Fact 1. $x^{2^m}+x = T_m(T_m+1) \Rightarrow T_m(\alpha)\in F_2 \,\,\forall \alpha\in F_{2^m}$
Fact 2. Let all irreducible factors of $f$ have degree $d$. Then $T_{kd}(\alpha) \mod f_i\in F_2 \,\,\forall i \,\,\forall \alpha\in R$

Now one can modify a probabilistic algorithm of equal-degree splitting: instead of computing $b=a^{(q^d-1)/2}\mathrm{rem} f$ one have to compute $b = T_{kd}(a)\mathrm{rem} f$.

_____________________

Proof of Fact 1.

1) First note that $(x_1+...+x_k)^{2^n} = x_1^{2^n}+...+x_k^{2^n} \,\, \forall x_i\in F_{2^m}$. It can be proved by induction on $n$. For $n=0$ and $n=1$ it is obvious. Assuming that this is true for $n-1$ one can get: $(x_1+...+x_k)^{2^n}=\left((x_1+...+x_k)^{2^{n-1}}\right)^2 = (x_1^{2^{n-1}}+...+x_k^{2^{n-1}})^2=x_1^{2^n}+...+x_k^{2^n}$

2) Then note that $a^q = a \,\, \forall a\in F_q$

3) Finally,    $T_m(\alpha)(T_m(\alpha)+1)=(T_m(\alpha))^2+T_m(\alpha) =$
                    $(\alpha^{2^{m-1}}+\alpha^{2^{m-1}}...+\alpha)^2+\alpha^{2^{m-1}}+...+\alpha^2+\alpha=$
                    $\alpha^{2^m}+\alpha^{2^{m-1}}...+\alpha^2+\alpha^{2^{m-1}}+...+\alpha^2+\alpha=$
                    $\alpha^{2^m}+\alpha=\alpha+\alpha=0 \,\, \forall \alpha\in F_{2^m}$
It means that $T_m(\alpha) = 0$ or $T_m(\alpha) = 1$, i.e. $T_m(\alpha)\in F_2\,\,\forall \alpha\in F_{2^m}$

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.