Engineering / Mathematics — Finite Fields
Equal Degree Factorization
Splitting a product of same-degree irreducible factors by random splitting, and the success probability.
Executive summary
Equal degree factorisation splits a polynomial known to be a product of irreducibles all of the same degree. It is the only randomised stage of finite field factorisation.
The method exploits the product decomposition of the quotient algebra: a random element raised to a suitable power lands differently in different components, and a gcd separates them.
Learning objectives
- State the splitting procedure for odd characteristic.
- Compute the success probability.
- Handle characteristic two separately.
01The idea
If f is a product of r distinct irreducibles each of degree d, then the quotient algebra is a product of r copies of F_{q^d}.
F_q[X]/(f) ≅ F_{q^d} × ··· × F_{q^d} (r copies)A random element has independent components. Raising it to the power (q^d − 1)/2 gives ±1 in each component, essentially independently, so subtracting 1 makes some components zero and others not. The gcd with f then picks out exactly the factors where it vanished.
02The algorithm
Equal degree splitting, odd q
f, a product of r irreducibles of equal degree da proper factor of f- Given f, a product of r > 1 irreducibles each of degree d.
- Repeat:
- Choose a random polynomial a of degree less than deg f.
- Compute g = gcd(a, f); if g ≠ 1, it is a proper factor — return it.
- Compute b = a^{(q^d − 1)/2} mod f.
- Compute g = gcd(b − 1, f).
- If 1 < deg g < deg f, return g as a proper factor.
- Recurse on g and f/g until all factors are irreducible.
expected O(d n² log q) field operationsSuccess probability
Each attempt splits f with probability at least 1/2, and for r = 2 exactly 1/2.
Hence the expected number of attempts is at most 2.
The bound comes from counting: the element's component values are essentially independent signs, and a split occurs unless all components agree. With r components that happens with probability about 2^{1−r}.
03Characteristic two
The replacement uses the trace map instead of the square root of unity.
Equal degree splitting, q = 2^m
f over F_{2^m}, product of equal-degree irreduciblesa proper factor- Choose a random a of degree less than deg f.
- Compute the trace-like element t = a + a² + a⁴ + ... + a^{2^{md−1}} mod f.
- Compute g = gcd(t, f).
- If 1 < deg g < deg f, return g; otherwise retry.
expected O(d n² m) field operationsThe trace map takes values 0 or 1 in each component, playing the same role the sign did in odd characteristic. The success probability is again at least one half.
This split into two cases is characteristic of finite field algorithms: characteristic two is both the most useful case in practice and the one requiring separate treatment, because the element −1 equals 1 and arguments relying on their distinctness fail.
04Frequently asked questions
Why is this stage randomised when the others are not?
Because there is no known deterministic way to distinguish components of the quotient algebra efficiently. Deterministic algorithms exist but depend on the generalised Riemann hypothesis or are far slower.
Does the gcd with a itself ever succeed?
Occasionally — if the random a happens to share a factor with f. It costs one gcd to check and returns a factor for free when it does, so the check is worth keeping.
What if the degree d is unknown?
It comes from the distinct degree stage, which is why the two run in sequence. Equal degree factorisation requires knowing d to set the exponent correctly.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 471-474.
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.