Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 20:37, 11 April 2020

Revision as of 15:10, 13 July 2020

Line 8:

===Background===

The Cantor–Zassenhaus algorithm takes as input a squarefree polynomial <math>f(x)</math> (i.e. one with no repeated factors) of degree ''n'' with coefficients in a finite field <math>\mathbb{F}_q</math> whose [[irreducible polynomial]] factors are all of equal degree (algorithms exist for efficiently factoring arbitrary polynomials into a product of polynomials satisfying these conditions, for instance, <math>f(x)/Gcd\gcd(f(x),f'(x))</math> is a squarefree polynomial with the same factors as <math>f(x)</math>, so that the Cantor–Zassenhaus algorithm can be used to factor 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 polynomials (recalling that the [[ring (mathematics)|ring]] of polynomials over any 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 ''d'', 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 ''R'' to ''S'', say <math>\phi</math>, maps a polynomial <math>g(x) \in R</math> to the ''s''-tuple of its reductions modulo each of the <math>p_i(x)</math>, i.e. if:

: <math>

\begin{align}

g(x) & {} \equiv g_1(x) \pmod{p_1(x)}, \\

Line 33:

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 |\mid a_i(x) = 0 \}, </math>

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

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

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