The Cantor–Zassenhaus algorithm takes as input a squarefree polynomial of degree n with coefficients in a finite field whose irreducible polynomialfactors are all of equal degree. 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. All possible factors of are contained within the factor ring . If we suppose that has irreducible factors, all of degree d, then this factor ring is isomorphic to the direct product of factor rings. The isomorphism from R to S, say, maps a polynomial to the s-tuple of its reductions modulo each of the, i.e. if: 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: where is the reduction of modulo as before, and if any two of the following three sets is non-empty: then there exist the following non-trivial factors of :
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. Select a random polynomial such that. Set and compute. Since is an isomorphism, we have : 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 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.
