Cantor-Zassenhaus algorithm
Encyclopedia
In 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 GCD
computations. It was invented by D. Cantor and Hans Zassenhaus in 1981.
It is arguably the dominant algorithm for solving the problem, having replaced the earlier Berlekamp's algorithm
of 1967. It is currently implemented in many well-known computer algebra system
s, including PARI/GP
.
(i.e. one with no repeated factors) of degree n with coefficients in a finite field 
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
with coefficients in the same field such that 
divides 
. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of 
into powers of irreducible polynomials (recalling that the ring
of polynomials over a finite field is a unique factorisation domain).
All possible factors of
are contained within the factor ring
. If we suppose that 
has irreducible factors 
, all of degree d, then this factor ring is isomorphic to the direct product
of factor rings
. The isomorphism from R to S, say 
, maps a polynomial 
to the s-tuple of its reductions modulo each of the 
, i.e. if:
then
. It is important to note the following at this point, as it shall be of critical importance later in the algorithm: Since the 
are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree 
.
is a polynomial satisfying:
where
is the reduction of 
modulo 
as before, and if any two of the following three sets is non-empty:
then there exist the following non-trivial factors of
:
above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field 
is of odd-characteristic. The process can be generalised to characteristic 2 fields in a fairly straightforward way: Select a random polynomial 
such that 
. Set 
and compute 
. Since 
is an isomorphism, we have (using our now-established notation):
Now, each
is an element of a field of order 
, as noted earlier. The multiplicative subgroup of this field has order 
and so, unless 
, we have 
for each i and hence 
for each i. If 
, then of course 
. Hence 
is a polynomial of the same type as 
above. Further, since 
, at least two of the sets 
and C 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
.
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 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.
Computational mathematics
Computational mathematics involves mathematical research in areas of science where computing plays a central and essential role, emphasizing algorithms, numerical methods, and symbolic methods. Computation in the research is prominent. Computational mathematics emerged as a distinct part of applied...
algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, the Cantor–Zassenhaus algorithm is a well known method for factorising polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s over finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
s (also called Galois fields).
The algorithm consists mainly of exponentiation and polynomial GCD
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
computations. It was invented by D. Cantor and Hans Zassenhaus in 1981.
It is arguably the dominant algorithm for solving the problem, having replaced the earlier Berlekamp's algorithm
Berlekamp's algorithm
In mathematics, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials over finite fields . The algorithm consists mainly of matrix reduction and polynomial GCD computations. It was invented by Elwyn Berlekamp in 1967...
of 1967. It is currently implemented in many well-known computer algebra system
Computer algebra system
A computer algebra system is a software program that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form.-Symbolic manipulations:...
s, including PARI/GP
PARI/GP
PARI/GP is a computer algebra system with the main aim of facilitating number theory computations. It is free software; versions 2.1.0 and higher are distributed under the GNU General Public License...
.
Background
The Cantor–Zassenhaus algorithm takes as input a squarefree polynomial (i.e. one with no repeated factors) of degree n with coefficients in a finite field whose irreducible polynomialIrreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
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
with coefficients in the same field such that divides . The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of into powers of irreducible polynomials (recalling that the ringRing (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
of polynomials over a finite field is a unique factorisation domain).
All possible factors of
are contained within the factor ring. If we suppose that has irreducible factors , all of degree d, then this factor ring is isomorphic to the direct productDirect product
In mathematics, one can often define a direct product of objectsalready known, giving a new one. This is generally the Cartesian product of the underlying sets, together with a suitably defined structure on the product set....
of factor rings
. The isomorphism from R to S, say , maps a polynomial to the s-tuple of its reductions modulo each of the , i.e. if:then
. It is important to note the following at this point, as it shall be of critical importance later in the algorithm: Since the are each irreducible, each of the factor rings in this direct sum is in fact a field. These fields each have degree .Core result
The core result underlying the Cantor–Zassenhaus algorithm is the following: If is a polynomial satisfying:
where
is the reduction of modulo as before, and if any two of the following three sets is non-empty:
then there exist the following non-trivial factors of
:
Algorithm
The Cantor–Zassenhaus algorithm computes polynomials of the same type as above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field is of odd-characteristic. The process can be generalised to characteristic 2 fields in a fairly straightforward way: Select a random polynomial such that . Set and compute . Since is an isomorphism, we have (using our now-established notation):Now, each
is an element of a field of order , as noted earlier. The multiplicative subgroup of this field has order and so, unless , we have for each i and hence for each i. If , then of course . Hence is a polynomial of the same type as above. Further, since , at least two of the sets and C 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 domainEuclidean domain
In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm...
, we may compute these GCDs using the Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
.
Applications
One important application of the Cantor–Zassenhaus algorithm is in computing discrete logarithmDiscrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
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 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.