Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 10:49, 30 May 2008

Latest revision as of 11:15, 29 March 2025

(50 intermediate revisions by 40 users not shown)

Line 1:

{{Short description|Algorithm for factoring polynomials over finite fields}}

In [[mathematics]], particularly [[computer algebra|computational algebra]], the Cantor-Zassenhaus algorithm is a well known method for factorising [[polynomial]]s over [[finite field]]s (also called Galois fields).

In [[Computational mathematics|computational]] [[Abstract algebra|algebra]], the '''Cantor–Zassenhaus algorithm''' is a method for factoring [[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[[David G. Cantor]] and [[Zassenhaus|Hans Zassenhaus]] in 1981. {{r|cz}}

It is arguably the dominant algorithm for solving the problem, having replaced the earlier [[Berlekamp's algorithm]] of 1967.{{r|Grenet}}{{r|vdh}} It is currently implemented in many well-known [[computer algebra system]]s, includinglike [[PARI/GP]].

==Overview==

===Background===

The Cantor-ZassenhausCantor–Zassenhaus algorithm takes as input a squarefree[[square-free 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 factorisingfactoring arbitrary polynomials into a product of polynomials satisfying these conditions, for instance, <math>f(x)/\gcd(f(x),f'(x))</math> is a squarefree polynomial with the same factors as <math>f(x)</math>, so that the Cantor-ZassenhausCantor–Zassenhaus algorithm can be used to factorisefactor 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 finiteany 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 sumproduct]] of factor rings <math>S = \bigoplus_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>g(x) \equiv g_1(x) \pmod{p_1(x)}</math>,

\begin{align}

:<math>g(x) & {} \equiv g_2g_1(x) \pmod{p_2p_1(x)}</math>, \\

g(x) & {} \equiv g_2(x) \pmod{p_2(x)}, \\

:<math>& {} \ \ \vdots</math> \\

g(x) & {} \equiv g_s(x) \pmod{p_s(x)},

\end{align}

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

</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 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>

: <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,

: <math>a_i(x) \in \{0,-1,1\}\text{ for }i=1,2,\ldots, s,</math>

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

: <math>A = \{ i | a_i(x) = 0 \} </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>B = \{ i | a_i(x) = -1 \} </math>,

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

: <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>:

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

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

: <math>\gcd(f(x),a(x)+1) = \prod_{i \in C} 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-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(the process can be generalised to characteristic 2 fields in a fairly straightforward way:.{{r|es}} 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, gb^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==

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 beis accessedimplemented in the PARI/GP packagecomputer usingalgebra system as the [http://pari.math.u-bordeaux.fr/dochtml/html-stable/Arithmetic_functions.html#factormod factormod()] function (formerly [http://pari.math.u-bordeaux.fr/dochtml/html-stable/Arithmetic_functions.html#factorcantor factorcantor()] command).

==See also==

*[[Polynomial factorization|Polynomial factorisation]]

*[[Factorization of polynomials over finite fields]]

*[[Berlekamp's algorithm]]

==References==

{{reflist|refs=

* David G. Cantor and Hans Zassenhaus. "A New Algorithm for Factoring Polynomials Over Finite Fields". Mathematics of Computation, 36:587-592, 1981.

<ref name=cz>{{citation

| last1 = Cantor | first1 = David G. | author1-link = David G. Cantor

| last2 = Zassenhaus | first2 = Hans | author2-link = Hans Zassenhaus

| date = April 1981

| doi = 10.1090/S0025-5718-1981-0606517-5

| issue = 154

| journal = [[Mathematics of Computation]]

| jstor = 2007663

| mr = 606517

| pages = 587–592

| title = A new algorithm for factoring polynomials over finite fields

| volume = 36| doi-access = free

}}</ref>

<ref name=es>{{citation

| last1 = Elia | first1 = Michele

| last2 = Schipani | first2 = Davide

| arxiv = 1012.5322

| doi = 10.21136/mb.2015.144395

| issue = 3

| journal = Mathematica Bohemica

| pages = 271–290

| publisher = Institute of Mathematics, Czech Academy of Sciences

| title = Improvements on the Cantor–Zassenhaus factorization algorithm

| volume = 140

| year = 2015}}</ref>

<ref name=Grenet>{{citation

| last1 = Grenet | first1 = B.

| last2 = van der Hoeven | first2 = Joris | author2-link = Joris van der Hoeven

| last3 = Lecerf | first3 = G.

| date = 2016

| journal = Applicable Algebra in Engineering, Communication and Computing

| volume = 27

| pages = 237–257

| title = Deterministic root finding over finite fields using Graeffe transforms

}}</ref>

<ref name=vdh>{{citation

| last1 = van der Hoeven| first1 = Joris | author1-link = Joris van der Hoeven

| last2 = Monagan| first2 = Michael

| date = 2021

| journal = ACM Communications in Computer Algebra

| volume = 54

| issue = 3

| pages = 65–85

| title = Computing one billion roots using the tangent Graeffe method

}}</ref>

}}

==External links==

*https://web.archive.org/web/20200301213349/http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/

{{DEFAULTSORT:Cantor-Zassenhaus algorithm}}

[[Category:Computer algebra]]

[[Category:Finite fields]]

[[Category:Polynomial factorization algorithms]]

[[fr:Algorithme de Cantor-Zassenhaus]]