Cantor–Zassenhaus algorithm

The Cantor–Zassenhaus algorithm takes as input a square-free polynomial ${\displaystyle f(x)}$ (i.e. one with no repeated factors) of degree n with coefficients in a finite field ${\displaystyle \mathbb {F} _{q}}$ whose irreducible polynomial factors are all of equal degree (algorithms exist for efficiently factoring arbitrary polynomials into a product of polynomials satisfying these conditions, for instance, ${\displaystyle f(x)/\gcd(f(x),f'(x))}$ is a squarefree polynomial with the same factors as ${\displaystyle f(x)}$, so that the Cantor–Zassenhaus algorithm can be used to factor arbitrary polynomials). It gives as output a polynomial ${\displaystyle g(x)}$ with coefficients in the same field such that ${\displaystyle g(x)}$ divides ${\displaystyle f(x)}$. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of ${\displaystyle f(x)}$ into powers of irreducible polynomials (recalling that the ring of polynomials over any field is a unique factorisation domain).

All possible factors of ${\displaystyle f(x)}$ are contained within the factor ring ${\displaystyle R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}}$. If we suppose that ${\displaystyle f(x)}$ has irreducible factors ${\displaystyle p_{1}(x),p_{2}(x),\ldots ,p_{s}(x)}$, all of degree d, then this factor ring is isomorphic to the direct product of factor rings ${\displaystyle S=\prod _{i=1}^{s}{\frac {\mathbb {F} _{q}[x]}{\langle p_{i}(x)\rangle }}}$. The isomorphism from R to S, say ${\displaystyle \phi }$, maps a polynomial ${\displaystyle g(x)\in R}$ to the s-tuple of its reductions modulo each of the ${\displaystyle p_{i}(x)}$, i.e. if:

${\displaystyle {\begin{aligned}g(x)&{}\equiv g_{1}(x){\pmod {p_{1}(x)}},\\g(x)&{}\equiv g_{2}(x){\pmod {p_{2}(x)}},\\&{}\ \ \vdots \\g(x)&{}\equiv g_{s}(x){\pmod {p_{s}(x)}},\end{aligned}}}$

then ${\displaystyle \phi (g(x)+\langle f(x)\rangle )=(g_{1}(x)+\langle p_{1}(x)\rangle ,\ldots ,g_{s}(x)+\langle p_{s}(x)\rangle )}$. It is important to note the following at this point, as it shall be of critical importance later in the algorithm: Since the ${\displaystyle p_{i}(x)}$ are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree ${\displaystyle q^{d}}$.

The core result underlying the Cantor–Zassenhaus algorithm is the following: If ${\displaystyle a(x)\in R}$ is a polynomial satisfying:

${\displaystyle a(x)\neq 0,\pm 1}$

${\displaystyle a_{i}(x)\in \{0,-1,1\}{\text{ for }}i=1,2,\ldots ,s,}$

where ${\displaystyle a_{i}(x)}$ is the reduction of ${\displaystyle a(x)}$ modulo ${\displaystyle p_{i}(x)}$ as before, and if any two of the following three sets is non-empty:

${\displaystyle A=\{i\mid a_{i}(x)=0\},}$

${\displaystyle B=\{i\mid a_{i}(x)=-1\},}$

${\displaystyle C=\{i\mid a_{i}(x)=1\},}$

then there exist the following non-trivial factors of ${\displaystyle f(x)}$:

${\displaystyle \gcd(f(x),a(x))=\prod _{i\in A}p_{i}(x),}$

${\displaystyle \gcd(f(x),a(x)+1)=\prod _{i\in B}p_{i}(x),}$

${\displaystyle \gcd(f(x),a(x)-1)=\prod _{i\in C}p_{i}(x).}$

The Cantor–Zassenhaus algorithm computes polynomials of the same type as ${\displaystyle a(x)}$ above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field ${\displaystyle \mathbb {F} _{q}}$ is of odd-characteristic (the process can be generalised to characteristic 2 fields in a fairly straightforward way ). Select a random polynomial ${\displaystyle b(x)\in R}$ such that ${\displaystyle b(x)\neq 0,\pm 1}$. Set ${\displaystyle m=(q^{d}-1)/2}$ and compute ${\displaystyle b(x)^{m}}$. Since ${\displaystyle \phi }$ is an isomorphism, we have (using our now-established notation):

${\displaystyle \phi (b(x)^{m})=(b_{1}^{m}(x)+\langle p_{1}(x)\rangle ,\ldots ,b_{s}^{m}(x)+\langle p_{s}(x)\rangle ).}$

Now, each ${\displaystyle b_{i}(x)+\langle p_{i}(x)\rangle }$ is an element of a field of order ${\displaystyle q^{d}}$, as noted earlier. The multiplicative subgroup of this field has order ${\displaystyle q^{d}-1}$ and so, unless ${\displaystyle b_{i}(x)=0}$, we have ${\displaystyle b_{i}(x)^{q^{d}-1}=1}$ for each i and hence ${\displaystyle b_{i}(x)^{m}=\pm 1}$ for each i. If ${\displaystyle b_{i}(x)=0}$, then of course ${\displaystyle b_{i}(x)^{m}=0}$. Hence ${\displaystyle b(x)^{m}}$ is a polynomial of the same type as ${\displaystyle a(x)}$ above. Further, since ${\displaystyle b(x)\neq 0,\pm 1}$, at least two of the sets ${\displaystyle A,B}$ and C are non-empty and by computing the above GCDs we may obtain non-trivial factors. Since the ring of polynomials over a field is a Euclidean domain, we may compute these GCDs using the Euclidean algorithm.