Polynomial Factorisation
Distinct Degree Factorisation
Separating irreducible factors by degree using GCDs against Frobenius powers, and the early-abort strategies that make it fast.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0564
Distinct degree factorisation separates the irreducible factors of a squarefree polynomial according to their degree. It is deterministic and rests on a single clean fact about finite fields.
The governing fact
The polynomial X to the q to the d, minus X, is exactly the product of all monic irreducible polynomials whose degree divides d.
The algorithm
Distinct degree factorisation
- InitialiseStart with the squarefree input and the polynomial X.
- Apply FrobeniusRaise the current tracker to the q-th power modulo the remaining input.
- Take the GCDThe GCD with the remaining input is the product of all irreducible factors of the current degree.
- Divide outRemove that product from the remaining input.
- AdvanceIncrement the degree and repeat.
Early termination
Irreducibility testing
The same machinery gives a fast irreducibility test without producing any factors: a polynomial of degree d is irreducible exactly when it divides the Frobenius polynomial at d and shares no factor with any smaller one, which reduces to checking the prime divisors of d.
| Task | Cost |
|---|---|
| Full distinct degree factorisation | Up to half the degree many Frobenius applications |
| Irreducibility test only | One Frobenius power plus a GCD for each prime divisor of the degree |
| Finding one root | A single GCD at degree one — see root finding |
Precomputing Frobenius
Output
The output is a set of polynomials, each a product of irreducibles of a single known degree. Separating those requires the probabilistic stage — see equal degree splitting.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.4.3. 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.