This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Cantor–Zassenhaus algorithm" – news ·newspapers ·books ·scholar ·JSTOR(November 2025) (Learn how and when to remove this message)

Incomputationalalgebra, theCantor–Zassenhaus algorithm is a method for factoringpolynomials overfinite fields (also called Galois fields).

The algorithm consists mainly of exponentiation and polynomialGCD computations. It was invented byDavid G. Cantor andHans Zassenhaus in 1981.^[1]

It is arguably the dominant algorithm for solving the problem, having replaced the earlierBerlekamp's algorithm of 1967.^[2][3] It is currently implemented in manycomputer algebra systems likePARI/GP.

The Cantor–Zassenhaus algorithm takes as input asquare-free polynomial${\displaystyle f(x)}$ (i.e. one with no repeated factors) of degreen with coefficients in a finite field${\displaystyle {\mathbb{F}}_q}$ whoseirreducible polynomial factors are all of equal degree (algorithms exist for efficiently factoring arbitrary polynomials into a product of polynomials satisfying these conditions, for instance,${\displaystyle f(x)/gcd(f(x),f^{\prime }(x))}$ is a squarefree polynomial with the same factors as${\displaystyle f(x)}$, so that the Cantor–Zassenhaus algorithm can be used to factor arbitrary polynomials). It gives as output a polynomial${\displaystyle g(x)}$ with coefficients in the same field such that${\displaystyle g(x)}$ divides${\displaystyle f(x)}$. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of${\displaystyle f(x)}$ into powers of irreducible polynomials (recalling that thering of polynomials over any field is aunique factorisation domain).

All possible factors of${\displaystyle f(x)}$ are contained within thefactor ring${\displaystyle R=\frac{{\mathbb{F}}_q[x]}{⟨f(x)⟩}}$. If we suppose that${\displaystyle f(x)}$ has irreducible factors${\displaystyle p_1(x),p_2(x),\dots ,p_s(x)}$, all of degreed, then this factor ring is isomorphic to thedirect product of factor rings${\displaystyle S=\prod _{i=1}^s\frac{{\mathbb{F}}_q[x]}{⟨p_i(x)⟩}}$. The isomorphism fromR toS, say${\displaystyle \varphi }$, maps a polynomial${\displaystyle g(x)\in R}$ to thes-tuple of its reductions modulo each of the${\displaystyle p_i(x)}$, i.e. if:

then${\displaystyle \varphi (g(x)+⟨f(x)⟩)=(g_1(x)+⟨p_1(x)⟩,\dots ,g_s(x)+⟨p_s(x)⟩)}$. It is important to note the following at this point, as it shall be of critical importance later in the algorithm: Since the${\displaystyle p_i(x)}$ are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree${\displaystyle q^d}$.

The core result underlying the Cantor–Zassenhaus algorithm is the following: If${\displaystyle a(x)\in R}$ is a polynomial satisfying:

${\displaystyle a(x)\ne 0,\pm 1}$

${\displaystyle a_i(x)\in \{0,-1,1\}\text{ for }i=1,2,\dots ,s,}$

where${\displaystyle a_i(x)}$ is the reduction of${\displaystyle a(x)}$ modulo${\displaystyle p_i(x)}$ as before, and if any two of the following three sets is non-empty:

${\displaystyle A=\{i\mid a_i(x)=0\},}$

${\displaystyle B=\{i\mid a_i(x)=-1\},}$

${\displaystyle C=\{i\mid a_i(x)=1\},}$

then there exist the following non-trivial factors of${\displaystyle f(x)}$:

${\displaystyle gcd(f(x),a(x))=\prod _{i\in A}{p}_i(x),}$

${\displaystyle gcd(f(x),a(x)+1)=\prod _{i\in B}{p}_i(x),}$

${\displaystyle gcd(f(x),a(x)-1)=\prod _{i\in C}{p}_i(x).}$

The Cantor–Zassenhaus algorithm computes polynomials of the same type as${\displaystyle a(x)}$ above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field${\displaystyle {\mathbb{F}}_q}$ is of odd-characteristic (the process can be generalised to characteristic 2 fields in a fairly straightforward way.^[4] Select a random polynomial${\displaystyle b(x)\in R}$ such that${\displaystyle b(x)\ne 0,\pm 1}$. Set${\displaystyle m=(q^d-1)/2}$ and compute${\displaystyle b(x{)}^m}$. Since${\displaystyle \varphi }$ is an isomorphism, we have (using our now-established notation):

${\displaystyle \varphi (b(x{)}^m)=(b_1^m(x)+⟨p_1(x)⟩,\dots ,b_s^m(x)+⟨p_s(x)⟩).}$

Now, each${\displaystyle b_i(x)+⟨p_i(x)⟩}$ is an element of a field of order${\displaystyle q^d}$, as noted earlier. The multiplicative subgroup of this field has order${\displaystyle q^d-1}$ and so, unless${\displaystyle b_i(x)=0}$, we have${\displaystyle b_i(x{)}^{q^d-1}=1}$ for eachi and hence${\displaystyle b_i(x{)}^m=\pm 1}$ for eachi. If${\displaystyle b_i(x)=0}$, then of course${\displaystyle b_i(x{)}^m=0}$. Hence${\displaystyle b(x{)}^m}$ is a polynomial of the same type as${\displaystyle a(x)}$ above. Further, since${\displaystyle b(x)\ne 0,\pm 1}$, at least two of the sets${\displaystyle A,B}$ andC are non-empty and by computing the above GCDs we may obtain non-trivial factors. Since the ring of polynomials over a field is aEuclidean domain, we may compute these GCDs using theEuclidean algorithm.

One important application of the Cantor–Zassenhaus algorithm is in computingdiscrete logarithms over finite fields of prime-power order. Computing discrete logarithms is an important problem inpublic key cryptography. For a field of prime-power order, the fastest known method is theindex 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.

The Cantor–Zassenhaus algorithm is implemented in the PARI/GP computer algebra system as thefactormod() function (formerlyfactorcantor()).

• Polynomial factorization
• Factorization of polynomials over finite fields

• Polynomial factorisation over finite fields, part 3: Final splitting (Cantor-Zassenhaus)

• Computer algebra
• Finite fields
• Polynomial factorization algorithms

• Articles needing additional references from November 2025
• All articles needing additional references
• Articles with short description
• Short description matches Wikidata