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.
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 formula_1 (i.e. one with no repeated factors) of degree "n" with coefficients in a finite field formula_2 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, formula_3 is a squarefree polynomial with the same factors as formula_1, so that the Cantor–Zassenhaus algorithm can be used to factor arbitrary polynomials). It gives as output a polynomial formula_5 with coefficients in the same field such that formula_5 divides formula_1. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of formula_1 into powers of irreducible polynomials (recalling that the ring of polynomials over any field is a unique factorisation domain).
All possible factors of formula_1 are contained within the factor ring
formula_10. If we suppose that formula_1 has irreducible factors formula_12, all of degree "d", then this factor ring is isomorphic to the direct product of factor rings formula_13. The isomorphism from "R" to "S", say formula_14, maps a polynomial formula_15 to the "s"-tuple of its reductions modulo each of the formula_16, i.e. if:
 formula_17
then formula_18. It is important to note the following at this point, as it shall be of critical importance later in the algorithm: Since the formula_16 are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree formula_20.
Core result.
The core result underlying the Cantor–Zassenhaus algorithm is the following: If formula_21 is a polynomial satisfying:
 formula_22
 formula_23
where formula_24 is the reduction of formula_25 modulo formula_16 as before, and if any two of the following three sets is non-empty:
 formula_27
 formula_28
 formula_29
then there exist the following non-trivial factors of formula_1:
 formula_31
 formula_32
 formula_33
Algorithm.
The Cantor–Zassenhaus algorithm computes polynomials of the same type as formula_25 above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field formula_2 is of odd-characteristic (the process can be generalised to characteristic 2 fields in a fairly straightforward way. Select a random polynomial formula_36 such that formula_37. Set formula_38 and compute formula_39. Since formula_14 is an isomorphism, we have (using our now-established notation):
formula_41
Now, each formula_42 is an element of a field of order formula_20, as noted earlier. The multiplicative subgroup of this field has order formula_44 and so, unless formula_45, we have formula_46 for each "i" and hence formula_47 for each "i". If formula_45, then of course formula_49. Hence formula_39 is a polynomial of the same type as formula_25 above. Further, since formula_52, at least two of the sets formula_53 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 discrete logarithms over finite fields of prime-power order. Computing discrete logarithms is an important problem in public key cryptography. For a field of prime-power order, the fastest known method is the 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;