In [[mathematics]], particularly [[computer algebra|computational algebra]], the '''Cantor-ZassenhausCantor–Zassenhaus algorithm'''<!-- --> is a well known method for factorising [[polynomial]]s over [[finite field]]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.
==Overview==
===Background===
The Cantor-ZassenhausCantor–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-ZassenhausCantor–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]]s (recalling that the [[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]]
===Core result===
The core result underlying the Cantor-ZassenhausCantor–Zassenhaus algorithm is the following: If <math>a(x) \in R</math> is a polynomial satisfying:
: <math>a(x) \neq 0, \pm 1 </math>
===Algorithm===
The Cantor-ZassenhausCantor–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 <math>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>
==Applications==
One important application of the Cantor-ZassenhausCantor–Zassenhaus algorithm is in computing [[discrete logarithm]]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-ZassenhausCantor–Zassenhaus algorithm.
==Implementation in computer algebra systems==
The Cantor-ZassenhausCantor–Zassenhaus algorithm may be accessed in the PARI/GP package using the [http://pari.math.u-bordeaux.fr/dochtml/html.stable/Arithmetic_functions.html#factorcantor factorcantor] command.
==See also==
|