Cantor-Zassenhaus split


Assume we want to factor a polynomialMathworldPlanetmathPlanetmathPlanetmath A𝔽p[X], where p is a prime and 𝔽p is the field with p elements. By using squarefree factorizationMathworldPlanetmath we can assume that A is squarefreeMathworldPlanetmath. The algorithmMathworldPlanetmath presented here now first splits A into polynomials Ai, where each irreduciblePlanetmathPlanetmath factor of Ai has degree i. The main part will then be to factor these polynomials. The Cantor-Zassenhaus split is an efficient algorithm to achieve that. It uses random numbers, nevertheless it always returns a correct factorization.

1 The distinct degree factorization

To completely factor A we will first find polynomials Ad with A=Ad, such that all irreducible factors of Ad have degree d. This is called the distinct degree factorization. Recall that if P𝔽p is an irreducible polynomialMathworldPlanetmath of degree d, then K:=𝔽p[X]/P(X)𝔽p[X] is a finite fieldMathworldPlanetmath with pd elements. So every xK*=K\{0} satisfies xpd-1=1, so every xK satisfies xpd=x, so P is a divisorMathworldPlanetmathPlanetmath of the polynomial Xpd-X𝔽p[X] and every irreducible factor of Xpd-X, which does not divide Xpe-X for some e<d. So we can easily find these Ad by introducing the series Bi with B1=A and

Bk+1=Agcd(Bk,Xpk-X).

Then Ad=gcd(Bd,Xpd-X).

2 The final splitting

We can now assume that we want to factor a polynomial A that has only irreducible factors of the known degree d.

2.1 Splitting for odd p

First assume that p is odd. Then we have the following

Lemma 1

If A is as above, then for any TFp[X] we have

A=gcd(A,T)gcd(A,Tpd-12-1)gcd(A,Tpd-12+1).

This is true because the roots of Xpd-X are exactly the elements of 𝔽pd and are all distinct in that field. So for any polynomial T𝔽p[X], the polynomial Tpd-T has also all elements of 𝔽pd as roots, so Xpd-X|Tpd-T. So as we have seen it is divisible by all irreducible polynomials of degree d, so it is divisible by A since A is squarefree. By noting that

Tpd-T=T(Tpd-12-1)(Tpd-12+1)

is a decomposition with pairwise coprime factors, the claimed identityPlanetmathPlanetmathPlanetmath follows.

Now one can simply choose a random polynomial T of degree less than 2d. Then it is likely that B:=gcd(A,Tpd-12-1) is a non-trivial divisor of A. We can then start over with B and A/B instead of A.

In this algorithm quite large powers of T need to be computed. It is of course sufficient (and useful) to compute these powers modulo A, in order to keep the degree of the appearing polynomials low.

To illustrate this idea, we choose d=1. This means that A is made up of different linear factors. Factorization is the achieved by finding zeroes. For this we could split 𝔽p into three disjoint sets M, N and {0}, such that MN{0}=𝔽p.Then we construct the polynomial

S=αM(X-α).

Obvioulsy it is now sufficient to factor the polynomials B:=gcd(A,S) and AB. If M and N were chosen wisely, these polynomials have lower degree than A. Now what is left is the choice of M and N. For the start it might be a good idea to consider the set of quadratic residuesMathworldPlanetmath in 𝔽p, so choosing

M={x𝔽p:(xp)=1},

where (xp) denotes the Legendre symbolMathworldPlanetmath. This choice is almost what we want. It is known that M and N are now of equal size and also we know that

S=Xp-12-1.

But if we want to apply the same method again to B and AB, we need some randomness. To achieve this, we simply do not consider the set of all quadratic residues, but the set

M={x𝔽p:(x-tp)=1},

where t𝔽p is some random element. This gives us the polynomial

S=(X-t)p-12-1.

Actually we have now chosen a random monic polynomialMathworldPlanetmath T of degree 1=2d-1 and are reducing the problem of factoring A to the problem of factoring B:=gcd(A,Tp-12-1) and AB, as it was described above.

2.2 Splitting for p=2

Let p=2. Lemma 1 does not work here because in the proof we use that

Tpd-1-1=(Tpd-12-1)(Tpd-12+1),

which requires p to be odd. However we can find something similar:

Lemma 2

Let

U(X)=X+X2+X4++X2d-1

and A as above. Then for any TF2[X] we have

A=gcd(A,UT)gcd(A,UT+1).

This is because (UT)2=T2+T4++T2d, so

(UT)(UT+1)=T2d-T

(we are in characteristic 2). Now this is a multiple of A and the identity follows.

This gives us an algorithm for factorization of A in the same way as above.

Title Cantor-Zassenhaus split
Canonical name CantorZassenhausSplit
Date of creation 2013-03-22 14:54:24
Last modified on 2013-03-22 14:54:24
Owner mathwizard (128)
Last modified by mathwizard (128)
Numerical id 8
Author mathwizard (128)
Entry type Algorithm
Classification msc 13M10
Classification msc 13P05
Classification msc 11C99
Classification msc 11Y99
Related topic SquarefreeFactorization
Defines distinct degree factorization