Engineering / Mathematics — Finite Fields
Berlekamp's Factorization Algorithm
Berlekamp's algorithm: the Berlekamp subalgebra, the kernel computation, and splitting by gcds.
Executive summary
Berlekamp's algorithm factors a squarefree polynomial by computing the kernel of a linear map. The kernel dimension equals the number of irreducible factors, so the count is known before any factor is found.
Splitting then uses the kernel elements, taking gcds against constant shifts.
Learning objectives
- Define the Berlekamp subalgebra and its dimension.
- State the algorithm and its cost.
- Explain when it is preferred over Cantor-Zassenhaus.
01The Berlekamp subalgebra
Berlekamp subalgebra
For squarefree f over F_q, the set
B = {v ∈ F_q[X]/(f) : v^q = v}.
These are the elements fixed by the Frobenius map on the quotient algebra.
Dimension equals the factor count
If f has r distinct irreducible factors, then B is an F_q-vector space of dimension r.
The reason is the product decomposition. Since f is squarefree, the quotient algebra is a product of r fields, and an element is fixed by Frobenius exactly when each component lies in F_q. Choosing one base field element per component gives q^r such elements, a space of dimension r.
02The algorithm
Berlekamp factorisation
squarefree monic f of degree n over F_qthe complete factorisation of f- Verify f is squarefree; if not, run squarefree decomposition first.
- Build the matrix Q whose columns are the coordinates of X^{iq} mod f, for i = 0, ..., n−1.
- Compute the kernel of Q − I; its dimension is r, the number of factors.
- If r = 1, f is irreducible — return it.
- For each non-constant basis element v of the kernel:
- For each c in F_q, compute gcd(f, v − c).
- Collect the non-trivial gcds as factors.
- Recurse on any factor that is still reducible.
O(n³ + qrn²) field operationsComplete splitting
For a non-constant v ∈ B, f = ∏_{c ∈ F_q} gcd(f, v − c), and the factors are separated according to the value v takes in each component.
03Cost and applicability
| Field size | Berlekamp | Cantor-Zassenhaus |
|---|---|---|
| q = 2 | Excellent — bit operations | Competitive |
| Small q | Good | Good |
| Large q | Poor — the q factor dominates | Preferred, only log q |
| Large n | Poor — cubic elimination | Preferred, quadratic |
Over F₂ Berlekamp is particularly attractive: the linear algebra is over the two-element field, so elimination is word-parallel bit operations, and the splitting loop has only two constants to try.
The deeper value of the algorithm is conceptual. It shows that polynomial factorisation, apparently a question about polynomials, is a rank computation — and the reformulation is what makes the factor count available in advance.
04Frequently asked questions
Why is the kernel dimension the factor count?
Because the quotient algebra is a product of r fields when f is squarefree, and the Frobenius-fixed elements are those with each component in the base field. That gives one free coordinate per component, hence dimension r.
How is the matrix Q constructed?
By computing X^{iq} mod f for each i, which is a sequence of modular exponentiations or repeated Frobenius applications. Building it dominates the cost for large degree.
What if q is too large for the splitting loop?
Sample random constants rather than enumerating, or switch to Cantor-Zassenhaus entirely. Most implementations choose the algorithm based on q and n rather than committing to one.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 477-482.
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.