Polynomial Factorisation
Cantor-Zassenhaus Equal Degree Splitting
Splitting a product of irreducibles of equal degree by random elements, the probability analysis, and the characteristic two variant.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0565
The final stage of finite field factorisation separates irreducible factors that share a degree. No deterministic polynomial-time method is known; the standard algorithm is Las Vegas — always correct, with random running time.
The setting
The input is squarefree and known to be a product of irreducible factors all of the same degree d. By the Chinese remainder theorem the quotient ring is a product of copies of the field of size q^d, one per factor.
The odd characteristic method
Half the non-zero elements of a finite field are squares. Raising a random element to the power that tests squareness gives plus or minus one in each component, and the GCD separates them.
Cantor-Zassenhaus equal degree splitting
- Choose randomlyPick a random polynomial of degree below that of the input.
- ExponentiateRaise to the half-order power modulo the input.
- Subtract oneForm the difference from the identity.
- Take the GCDA non-trivial GCD splits the input.
- RecurseApply to both parts until all factors are separated.
Probability of success
Each component independently lands in one of two classes with probability close to one half, so a random choice fails to split only when all components agree.
Characteristic two
Cost
| Component | Cost |
|---|---|
| One trial | One modular exponentiation plus one GCD |
| Expected trials per split | About two |
| Total for r factors | Proportional to r splits |
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.4.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.