Cantor-Zassenhaus algorithm

Last Saturday I finished the first big part of my project: I ported Cantor-Zassenhaus algorithm with all helper functions from nmod_poly module to fmpz_mod_poly module.

I think it was an important part of my job because it helped me to familiarise myself with the code: I found some important differences between nmod and fmpz modules (I spent a lot of time debugging my stupid errors relates to these differences).

During the last month I got a good impression of the code of FLINT. I like it's clearness: every function has it's own file and detailed description, the function names are easy-to-understand (I mean that one can guess what the function should do according to it's name), pieces of code doing one distinct thing are organised in separate functions (so the complex algorithms don't look ugly).


Now I'm going to describe Cantor-Zassenhaus algorithm (the complete description can be found in Modern Computer Algebra book).

Input and output
The algorithm gets on input a nonconstant polynomial $P$ over a field $Z_q$ ($q$ is an odd prime number). On output it gives all monic irreducible factors of P with their multipliсities.

Short description
In brief the algorithm can be described as follows: in a cycle for $i=1,2,...$ it computes distinct-degree polynomial $g_i$ (a product of all squarefree irreducible factors of $P$ of degree $i$), then it decomposes $g_i$ into equal degree factors $f_{ij}$ (each of degree $i$) and for all $j$ removes the highest possible degree of $f_{ij}$ (say $e_{ij}$) from $P$ simply dividing $P$ by $f_{ij}$. The cycle continues for $P=P'$ ($P'$ is $P$ without $f_{ij}^{e_{ij}}$) while $\deg P' > 1$.

Distinct-degree factorisation
This algorithm is based on Fermat's little theorem, more precisely on the consequence of the following


Theorem. For any $d\geq 1 (x^{q^d}-x) \in F_q[x]$ is the product of all monic irreducible polynomials in $F_q[x]$ whose degree divides $d$.


Now we can easily construct an algorithm: for $d = 1, 2, ...$ compute $h = x^{q^d} - x$ and find $g=\gcd(h,f)$, continue this procedure for $f=\frac{f}{g}$ until $f=1$.


Equal-degree factorisation
It is a recursive algorithm: it calls a probabilistic procedure of finding a factor $g$ of a given degree of a polynomial $P$, then it removes the found factor $g$ from $P$ and calls itself for $P=\frac{P}{f}$.

Equal-degree splitting
It is a probabilistic procedure of finding a factor $g$ of a given degree of a polynomial $P$. It is based on the following 


Lemma. Let $q$ be an odd prime number. Then $a^{(q-1)/2}\in\{1,-1\} \,\,\, \forall a\in F_q^{*}$ ($F_q^{*}$  is a multiplicative group of  $F_q$). 


Let the polynomial $P$ have the degree $n=rd$ and every it's single factor have the degree $d$. Then the probabilistic algorithm is as follows: choose $a\in F_q[x]$ with $\deg a < n$ at random. If $\deg a = 0$ return "failure". Else compute $g_1=\gcd(a,f)$. If $\deg g_1 > 0$ return $g_1$. Else (if $\deg g_1 = 0$) compute $b=a^{(q^d-1)/2}\mathrm{rem} f$ (see Lemma) and $g_2=\gcd(b-1, f)$. If $g_2\neq 1, g_2\neq f$ return $g_2$, else return "failure".


Some technical remarks
To compute powers of q the binary exponentiation method can be applied.
To compute the gcd  euclidean method can be used.


According to my project proposal I'm out of schedule, so I would like to change the order of the next two algorithms and to continue now with "baby/giant step" algorithm (and to implement Berlekamp after it if there is time left).