Three phases, each solving a strictly easier problem than the last
Factoring over a finite field is completely solved in polynomial time, but not by a single algorithm. The standard pipeline first removes repeated factors, then groups the remaining irreducible factors by their degree, and only then separates factors of equal degree — the one phase that requires randomisation. Each phase reduces to GCD computations and modular exponentiation in the quotient ring.
Learning objectives
- Perform squarefree decomposition, including the characteristic-p special case.
- Separate factors by degree using gcd with xqd − x.
- Apply equal-degree splitting and analyse its success probability.
- Compare Berlekamp's method with the distinct-degree pipeline.
- Choose an approach based on the field size.
Section 01Phase 1: squarefree decomposition
If f has a repeated factor, that factor divides gcd(f, f′). Peeling off repeated factors by successive GCDs gives the squarefree decomposition. In characteristic p there is a complication: if f′ is identically zero then f is a p-th power.
- If f′ = 0, then f = g(xp) for some g. Take p-th roots of the coefficients — the Frobenius is a bijection on Fp — and recurse on g.
- Otherwise set c ← gcd(f, f′) and w ← f / c.
- Repeatedly extract gcd(w, c), which isolates factors of successive multiplicities.
- Output the list of (factor, multiplicity) pairs.
Over ℚ, f′ = 0 only for constants. Over Fp it happens for every p-th power, and code that omits this branch will divide by a zero polynomial or loop. This is one of the most frequently missed cases in finite-field code.
Section 02Phase 2: distinct-degree factorisation
The polynomial xqd − x is the product of all monic irreducibles whose degree divides d. Taking GCDs for d = 1, 2, 3, … therefore extracts the factors degree by degree.
- Set g ← f (squarefree) and h ← x.
- For d = 1, 2, 3, … while deg g ≥ 2d:
- Set h ← hq mod g. One Frobenius step; h now equals xq^d mod g.
- Set c ← gcd(g, h − x). If c ≠ 1, record c as the product of all irreducible factors of degree d, and set g ← g / c.
- If g ≠ 1, it is irreducible of degree greater than the last d tested; record it.
Each iteration raises the current h to the q-th power modulo g. Precomputing the matrix of the Frobenius map on the quotient ring turns each step into a matrix–vector product, which is the standard optimisation for repeated factorisations over the same field.
Section 03Phase 3: equal-degree splitting
A product of r distinct irreducibles all of degree d corresponds by the Chinese remainder theorem to a product of r copies of the field of qd elements. A random element raised to the power (qd − 1)/2 lands on ±1 independently in each component, so a GCD with the result splits the factors apart with high probability.
- If deg f = d, output f as irreducible and return.
- Choose a random a ∈ Fq[x] with deg a < deg f.
- Set b ← a(qd−1)/2 mod f.
- Set c ← gcd(f, b − 1). If c is trivial, return to step 2.
- Recurse on c and on f / c.
Every factor is confirmed by an exact GCD before being returned, so the algorithm never emits an incorrect factorisation. Randomisation affects only how long it takes.
Section 04Berlekamp's algorithm and method selection
Berlekamp's approach is entirely different: it computes the kernel of the map v ↦ vq − v on the quotient ring. The kernel dimension equals the number of irreducible factors, and each kernel element yields a splitting.
| Situation | Method | Reason |
|---|---|---|
| q small (say under 100) | Berlekamp | Deterministic; the search over field elements is cheap |
| q large | Distinct-degree plus Cantor–Zassenhaus | Berlekamp's search space scales with q; the randomised split does not |
| Only the number of factors is needed | Berlekamp kernel dimension | One linear algebra computation, no splitting required |
| Only irreducibility is in question | Degree test via Frobenius | Far cheaper than a full factorisation |
| Only the roots are needed | gcd with xq − x, then split | Avoids computing higher-degree factors entirely |
To test irreducibility of degree n it suffices to check that xqn = x modulo f and that gcd(f, xqn/ℓ − x) = 1 for each prime ℓ dividing n. No factors are produced — and none are needed.
ReferenceFrequently asked questions
Why must squarefree decomposition come first?
Because distinct-degree factorisation returns the product of the distinct irreducible factors of each degree, with multiplicities lost. Running it on a non-squarefree input silently discards multiplicity information and the reconstructed factorisation will not multiply back to the input.
How does this generalise to extension fields?
Directly: replace p by the field size q throughout. The only care needed is in the characteristic-2 case of equal-degree splitting, where the exponentiation must be replaced by the trace map because (q^d − 1)/2 is not an integer.
Can the same pipeline factor over Z/nZ for composite n?
No. Without a field the quotient ring has zero divisors, GCDs need not exist, and the factorisation is not unique. An attempted GCD that fails does, however, reveal a factor of n.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.