|
In [[Computational mathematics|computational]], particularly [[computerAbstract algebra|computational algebra]], the '''Cantor–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–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]]spolynomials (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]]
<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 product]] of factor rings <math>S = \prod_{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>
:<math>\phi(b(x)^m) = (b_1^m(x) + \langle p_1(x) \rangle, \ldots, b^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]].
==Applications==
| 