Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 20:11, 21 July 2006

Revision as of 20:12, 21 July 2006

Line 1:

In [[mathematics]], particularly [[computer algebra|computational algebra]], the Cantor-Zassenhaus algorithm is a well known method for factorising [[polynomial|polynomials]] over [[finite field|finite fields]] (aka [[galois field|Galois fields]]). The algorithm consists mainly of exponentiation and polynomial [[greatest common divisor|GCD]] computations. It was invented by D. Cantor and [[Zassenhaus|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 system|computer algebra systems]], including [[PARI-GP_computer_algebra_system|PARI-GP]].

==Overview==

Line 9 ⟶ 8:

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

:<math>g(x) \equiv g_1(x) \pmod{p_1(x)}</math>,

:<math>g(x) \equiv g_2(x) \pmod{p_2(x)}</math>,

:<math>\vdots</math>

:<math>g(x) \equiv g_s(x) \pmod{p_s(x)}</math>,

then <math>\phi(g(x) + \langle f(x) \rangle) = (g_1(x) + \langle p_1(x) \rangle, \ldots, g_s(x) + \langle p_s(x) \rangle)</math>. It is important to note the following at this point, as it shall be of critical importance later in the algorithm: Since the <math>p_i(x)</math> are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree <math>q^d</math>.

===Core Resultresult===

The core result underlying the Cantor-Zassenhaus algorithm is the following: If <math>a(x) \in R</math> is a polynomial satisfying:

*: <math>a(x) \neq 0, \pm 1 </math>

*: <math>a_i(x) \in \{0,-1,1\}</math> for <math>i=1,2,\ldots, n</math>, where <math>a_i(x)</math> is the reduction of <math>a(x)</math> modulo <math>p_i(x)</math> as before,

and if any two of the following three sets is non-empty:

*: <math>A = \{ i | a_i(x) = 0 \} </math>,

*: <math>B = \{ i | a_i(x) = -1 \} </math>,

*: <math>C = \{ i | a_i(x) = 1 \} </math>,

then there exist the following non-trivial factors of <math>f(x)</math>:

*: <math>\gcd(f(x),a(x) = \prod_{i \in A} p_i(x)</math>,

*: <math>\gcd(f(x),a(x)-1 = \prod_{i \in B} p_i(x)</math>,

*: <math>\gcd(f(x),a(x)+1 = \prod_{i \in C} p_i(x)</math>.

===Algorithm===

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

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

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

Line 42 ⟶ 41:

One important application of the Cantor-Zassenhaus algorithm is in computing [[discrete logarithm|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|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 Computercomputer Algebraalgebra Systemssystems==

The Cantor-Zassenhaus algorithm may be accessed in the GP-PARI package using the [http://pari.math.u-bordeaux.fr/dochtml/html.stable/Arithmetic_functions.html#factorcantor factorcantor] command.

==See Alsoalso==

*[[Polynomial factorization|Polynomial factorisation]]

*[[Berlekamp's algorithm]]