Algorithm for factoring polynomials over finite fields
In computational algebra, the Cantor–Zassenhaus algorithm is a method for factoring polynomials over finite fields (also called Galois fields).
The algorithm consists mainly of exponentiation and polynomial GCD computations. It was invented by David G. Cantor and Hans Zassenhaus in 1981.[1]
It is arguably the dominant algorithm for solving the problem, having replaced the earlier Berlekamp's algorithm of 1967. It is currently implemented in many computer algebra systems.
Overview
Background
The Cantor–Zassenhaus algorithm takes as input a square-free polynomial
(i.e. one with no repeated factors) of degree n with coefficients in a finite field
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,
is a squarefree polynomial with the same factors as
, so that the Cantor–Zassenhaus algorithm can be used to factor arbitrary polynomials). It gives as output a polynomial
with coefficients in the same field such that
divides
. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of
into powers of irreducible polynomials (recalling that the
unique factorisation domain
).
All possible factors of
are contained within the
factor ring
![{\displaystyle R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdd069c857c881ebb711c4aa51d5198f49a79806)
. If we suppose that
![{\displaystyle f(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074)
has irreducible factors
![{\displaystyle p_{1}(x),p_{2}(x),\ldots ,p_{s}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b78888a7e1af3cdb36ae90e6375adb0bfad59963)
, 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 }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4b2df97d1fad4914174a8279a5091c5177c3bfa)
. The isomorphism from
R to
S, say
![{\displaystyle \phi }](https://wikimedia.org/api/rest_v1/media/math/render/svg/72b1f30316670aee6270a28334bdf4f5072cdde4)
, maps a polynomial
![{\displaystyle g(x)\in R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11f42d1a018a7258492a77386f8aeba902f09053)
to the
s-tuple of its reductions modulo each of the
![{\displaystyle p_{i}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73d70f3bb2f1aba1ae2ebda770515b1005e27024)
, 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34a30e73b9e82348dcc9d859c1eab2a7592cdc84)
then
. It is important to note the following at this point, as it shall be of critical importance later in the algorithm: Since the
are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree
.
Core result
The core result underlying the Cantor–Zassenhaus algorithm is the following: If
is a polynomial satisfying:
![{\displaystyle a(x)\neq 0,\pm 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c36fda39fbc1a3a2bb0eea74e2ca12f05170386e)
![{\displaystyle a_{i}(x)\in \{0,-1,1\}{\text{ for }}i=1,2,\ldots ,s,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4fee0eef1755cce4fccfd35c05e4f64b7064eb6)
where
is the reduction of
modulo
as before, and if any two of the following three sets is non-empty:
![{\displaystyle A=\{i\mid a_{i}(x)=0\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31c37408626a892085fb40b8f60466db1e8a75e6)
![{\displaystyle B=\{i\mid a_{i}(x)=-1\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68ef211707630d3a589a0f28f1efb78e8acc6216)
![{\displaystyle C=\{i\mid a_{i}(x)=1\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/660cbee2aba24b6e113440f97a27373c66596ad7)
then there exist the following non-trivial factors of
:
![{\displaystyle \gcd(f(x),a(x))=\prod _{i\in A}p_{i}(x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c1fbfe2973f995f9d61bc5141d687b48fd6a08a)
![{\displaystyle \gcd(f(x),a(x)+1)=\prod _{i\in B}p_{i}(x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68ec6ed90771d1534b34db863f2c36e5522153fb)
![{\displaystyle \gcd(f(x),a(x)-1)=\prod _{i\in C}p_{i}(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2c5ea0b09e6491a7d5b11bc1e4adcb912e0478)
Algorithm
The Cantor–Zassenhaus algorithm computes polynomials of the same type as
above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field
is of odd-characteristic (the process can be generalised to characteristic 2 fields in a fairly straightforward way.[2] Select a random polynomial
such that
. Set
and compute
. Since
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 ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/682035fee00ada2b50a7418ed2fca007a24d27d7)
Now, each
is an element of a field of order
, as noted earlier. The multiplicative subgroup of this field has order
and so, unless
, we have
for each i and hence
for each i. If
, then of course
. Hence
is a polynomial of the same type as
above. Further, since
, at least two of the sets
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.
Applications
One important application of the Cantor–Zassenhaus algorithm is in computing
index calculus method
, which involves the factorisation of field elements. If we represent the prime-power order field in the usual way – that is, as polynomials over the prime order base field, reduced modulo an irreducible polynomial of appropriate degree – then this is simply polynomial factorisation, as provided by the Cantor–Zassenhaus algorithm.
Implementation in computer algebra systems
The Cantor–Zassenhaus algorithm is implemented in the PARI/GP computer algebra system as the factorcantor() function.
See also
References
External links