Polynomial Factorisation
The Berlekamp Factorisation Algorithm
Berlekamp's linear algebra approach to factoring over a finite field, the Berlekamp subalgebra, and when it outperforms the GCD pipeline.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0566
Berlekamp's algorithm factors a polynomial over a finite field by linear algebra rather than by GCD computations. It computes the number of irreducible factors before finding any of them, which the GCD pipeline cannot do.
The Berlekamp subalgebra
Consider the quotient ring by the input polynomial. Elements fixed by Frobenius form a subalgebra, and its dimension equals the number of distinct irreducible factors.
The algorithm
Berlekamp's algorithm
- Ensure squarefreeRun squarefree factorisation first.
- Build the Frobenius matrixCompute X to the q times i modulo f for each basis index, giving the matrix of the Frobenius map.
- Subtract the identityForm the matrix of Frobenius minus the identity.
- Compute the kernelBy elimination over the field. Its dimension is the factor count.
- SplitFor each non-constant kernel element, take GCDs of f with that element minus each field constant.
The splitting step
A non-constant element of the Berlekamp subalgebra takes a constant value in each component of the quotient ring. Taking the GCD of the input with that element minus each constant separates the factors according to those values.
Choosing between Berlekamp and the GCD pipeline
| Condition | Preferred method |
|---|---|
| Small field, moderate degree | Berlekamp — deterministic and fast |
| Large field | GCD pipeline; Berlekamp's splitting scales badly |
| High degree | GCD pipeline; the matrix is degree by degree |
| Factor count wanted without factors | Berlekamp |
| Irreducibility test only | Distinct degree is cheaper |
Beyond polynomials
The same kernel construction splits more general algebras over finite fields, which is precisely how algebra splitting is performed inside Buchmann-Lenstra prime decomposition.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.4.5. 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.