Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 09:18, 18 September 2006

Revision as of 05:01, 15 October 2006

Line 1:

In [[mathematics]], particularly [[computer algebra|computational algebra]], the Cantor-Zassenhaus algorithm is a well known method for factorising [[polynomial]]s over [[finite field|finite fields]]s (also called 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]]s, including [[PARI-GP_computer_algebra_systemGP computer algebra system|PARI-GP]].

==Overview==

===Background===

The Cantor-Zassenhaus algorithm takes as input a squarefree polynomial <math>f(x)</math> (i.e. one with no repeated factors) of degree <math>n</math> with coefficients in a finite field <math>\mathbb{F}_q</math> 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 <math>g(x)</math> with coefficients in the same field such that <math>g(x)</math> divides <math>f(x)</math>. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of <math>f(x)</math> into powers of [[irreducible polynomial|irreducible polynomials]]s (recalling that the [[ring_ring (mathematics)|ring]] of polynomials over a finite field is a [[unique factorisation ___domain]].

All possible factors of <math>f(x)</math> are contained within the [[factor ring]]

Line 43:

==Applications==

One important application of the Cantor-Zassenhaus algorithm is in computing [[discrete logarithm|discrete logarithms]]s 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 computer algebra systems==