CantorZassenhausalgoritmer

Cantor–Zassenhaus algorithm is a probabilistic method for factoring polynomials over finite fields. It was introduced by Gerhard Cantor and Hans Zassenhaus and remains a foundational technique in computational algebra for breaking polynomials in F_q[x] into irreducible factors. The algorithm requires the input polynomial to be square-free and works best as part of a larger factorization pipeline.

The method proceeds in two main phases. First, distinct-degree factorization (DDF) separates the polynomial into a product of factors, each consisting of all irreducible factors having the same degree. Over a finite field F_q, this is accomplished by exploiting the Frobenius endomorphism, computing gcds of the input with polynomials of the form x^{q^i} − x, to accumulate factors whose irreducible components have degree i.

Second, equal-degree factorization (EDF) takes each factor produced by the DDF phase, where all irreducible components have the same degree i, and splits it further into the individual irreducible factors of that degree. A common approach uses a randomization step: compute h ≡ x^{q^i} mod g for the current factor g, then form gcd(h − a, g) for random a in F_q. With nontrivial gcds, g is reduced into smaller factors; the process iterates until g splits into irreducibles.

The Cantor–Zassenhaus algorithm is a Las Vegas probabilistic algorithm with expected polynomial-time complexity in the degree of the polynomial and log q. It is implemented in many computer algebra systems and often serves as a standard subroutine in finite-field polynomial factorization, sometimes complemented by alternative methods for derandomization or for special field sizes.