Engineering / Mathematics — Finite Fields
Distinct Degree Factorization
Separating the irreducible factors of a polynomial by degree using gcds with Frobenius powers.
Executive summary
Distinct degree factorisation splits a squarefree polynomial into parts, each the product of all irreducible factors of a given degree, using the identity for X to the q to the d minus X.
It is deterministic and is the first stage of the Cantor-Zassenhaus algorithm.
Learning objectives
- State the identity underlying the method.
- Give the algorithm and its cost.
- Explain the early termination condition.
01The identity
Product of irreducibles by degree
Over F_q,
X^{q^d} − X = ∏ (all monic irreducible polynomials whose degree divides d).
This follows from the subfield characterisation: the roots of X^{q^d} − X are exactly the elements of F_{q^d}, and an element lies there exactly when its minimal polynomial has degree dividing d.
Taking a gcd with a target polynomial therefore extracts precisely the factors of degree dividing d. Sweeping d upwards and dividing out at each stage separates the factors by degree.
02The algorithm
Distinct degree factorisation
squarefree monic f over F_qfor each d, the product of all irreducible factors of degree d- Given squarefree monic f. Set h = X and d = 0.
- While deg f > 0:
- Increment d and set h = h^q mod f, by applying Frobenius.
- Compute g = gcd(h − X, f).
- If g ≠ 1, record g as the product of all degree-d factors, and set f = f/g.
- If d > deg(f)/2, record the remaining f as irreducible and stop.
- Return the list of (degree, product) pairs.
O(n² log q) field operations with a Frobenius matrixThe early termination is important and easy to omit. Once d exceeds half the remaining degree, no factor of degree d can be accompanied by another, so what remains must be irreducible.
03What it does and does not do
Squarefree decomposition
Remove repeated factors, so the input is squarefree.
Distinct degree factorisation
Separate by degree; deterministic.
Equal degree factorisation
Split each same-degree group into individual factors; randomised.
| Stage | Deterministic? | Output |
|---|---|---|
| Squarefree decomposition | Yes | Squarefree parts with multiplicities |
| Distinct degree | Yes | Products grouped by factor degree |
| Equal degree | No | Individual irreducible factors |
Only the third stage requires randomness, and only when a degree group contains more than one factor. Many polynomials factor completely after the deterministic stages, which is why implementations check after each stage rather than always running all three.
04Frequently asked questions
Why compute h^q by Frobenius rather than exponentiation?
Because Frobenius is a linear map with a precomputable matrix, so applying it is a matrix-vector product. General exponentiation to the q-th power would cost a factor of log q more.
What if the input is not squarefree?
The gcd computations misbehave and the degree separation is unreliable. Squarefree decomposition must run first, which is why it is the documented precondition.
Why is the early termination correct?
Because a polynomial of degree m with all factors of degree greater than m/2 can have only one factor. Once d passes that threshold, the remaining polynomial cannot decompose further.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 467-471.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.