Cantor–Zassenhaus algorithm

From Wikipedia, the free encyclopedia

In mathematics, particularly computational algebra, the Cantor–Zassenhaus algorithm is a well known method for factorising polynomials over finite fields (also called Galois fields).

The algorithm consists mainly of exponentiation and polynomial GCD computations. It was invented by D. 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 well-known computer algebra systems, including PARI/GP.

Contents

[edit] Overview

[edit] Background

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

All possible factors of f(x) are contained within the factor ring R = \frac{\mathbb{F}_q[x]}{\langle f(x) \rangle}. If we suppose that f(x) has irreducible factors p_1(x), p_2(x), \ldots, p_s(x), all of degree d, then this factor ring is isomorphic to the direct sum of factor rings S = \bigoplus_{i=1}^s \frac{\mathbb{F}_q[x]}{\langle p_i(x) \rangle}. The isomorphism from R to S, say φ, maps a polynomial g(x) \in R to the s-tuple of its reductions modulo each of the pi(x), i.e. if:

\begin{align} 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{align}

then \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 pi(x) are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree qd.

[edit] Core result

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

a(x) \neq 0, \pm 1
a_i(x) \in \{0,-1,1\} for i=1,2,\ldots, n,

where ai(x) is the reduction of a(x) modulo pi(x) as before, and if any two of the following three sets is non-empty:

A = {i | ai(x) = 0},
B = {i | ai(x) = − 1},
C = {i | ai(x) = 1},

then there exist the following non-trivial factors of f(x):

\gcd(f(x),a(x)) = \prod_{i \in A} p_i(x),
\gcd(f(x),a(x)-1) = \prod_{i \in B} p_i(x),
\gcd(f(x),a(x)+1) = \prod_{i \in C} p_i(x).

[edit] Algorithm

The Cantor–Zassenhaus algorithm computes polynomials of the same type as a(x) above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field \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 b(x) \in R such that b(x) \neq 0, \pm 1 . Set m = (qd − 1) / 2 and compute b(x)m. Since φ is an isomorphism, we have (using our now-established notation):

\phi(b(x)^m) = (b_1^m(x) + \langle p_1(x) \rangle, \ldots, g^m_s(x) + \langle p_s(x) \rangle,).

Now, each b_i(x) + \langle p_i(x)\rangle is an element of a field of order qd, as noted earlier. The multiplicative subgroup of this field has order qd − 1 and so, unless bi(x) = 0, we have b_i(x)^{q^d-1}=1 for each i and hence b_i(x)^m = \pm 1 for each i. If bi(x) = 0, then of course bi(x)m = 0. Hence b(x)m is a polynomial of the same type as a(x) above. Further, since b(x) \neq 0, \pm1, at least two of the sets 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.

[edit] 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.

[edit] Implementation in computer algebra systems

The Cantor–Zassenhaus algorithm may be accessed in the PARI/GP package using the factorcantor command.

[edit] See also

[edit] References

  • David G. Cantor and Hans Zassenhaus. "A New Algorithm for Factoring Polynomials Over Finite Fields". Mathematics of Computation, 36:587-592, 1981.
Languages