Assume we want to factor a polynomial , where is a prime and is the field with elements. By using squarefree factorization we can assume that is squarefree. The algorithm presented here now first splits into polynomials , where each irreducible factor of has degree . 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 we will first find polynomials with , such that all irreducible factors of have degree . This is called the distinct degree factorization. Recall that if is an irreducible polynomial of degree , then is a finite field with elements. So every satisfies , so every satisfies , so is a divisor of the polynomial and every irreducible factor of , which does not divide for some . So we can easily find these by introducing the series with and
2 The final splitting
We can now assume that we want to factor a polynomial that has only irreducible factors of the known degree .
2.1 Splitting for odd
First assume that is odd. Then we have the following
If is as above, then for any we have
This is true because the roots of are exactly the elements of and are all distinct in that field. So for any polynomial , the polynomial has also all elements of as roots, so . So as we have seen it is divisible by all irreducible polynomials of degree , so it is divisible by since is squarefree. By noting that
Now one can simply choose a random polynomial of degree less than . Then it is likely that is a non-trivial divisor of . We can then start over with and instead of .
In this algorithm quite large powers of need to be computed. It is of course sufficient (and useful) to compute these powers modulo , in order to keep the degree of the appearing polynomials low.
To illustrate this idea, we choose . This means that is made up of different linear factors. Factorization is the achieved by finding zeroes. For this we could split into three disjoint sets , and , such that .Then we construct the polynomial
Obvioulsy it is now sufficient to factor the polynomials and . If and were chosen wisely, these polynomials have lower degree than . Now what is left is the choice of and . For the start it might be a good idea to consider the set of quadratic residues in , so choosing
where denotes the Legendre symbol. This choice is almost what we want. It is known that and are now of equal size and also we know that
But if we want to apply the same method again to and , we need some randomness. To achieve this, we simply do not consider the set of all quadratic residues, but the set
where is some random element. This gives us the polynomial
2.2 Splitting for
Let . Lemma 1 does not work here because in the proof we use that
which requires to be odd. However we can find something similar:
and as above. Then for any we have
This is because , so
This gives us an algorithm for factorization of in the same way as above.
|Date of creation||2013-03-22 14:54:24|
|Last modified on||2013-03-22 14:54:24|
|Last modified by||mathwizard (128)|
|Defines||distinct degree factorization|