Berlekamp Factorization Algorithm

Purpose: Factor a polynomial over a finite field ${\mathbb{F}}_q$ in $O(n^3+n^2\log q)$ — deterministic for small $q$, and the classical answer to “factor this polynomial mod $p$”.

The Idea: the Berlekamp subalgebra

Suppose $f=f_1{f}_2\cdots f_k$ with distinct irreducible factors. By CRT,

${\mathbb{F}}_q[x]/(f)\cong {\prod }_{i=1}^k{\mathbb{F}}_q[x]/(f_i).$

Consider the Frobenius map $\varphi (g)=g^q-g(\mathrm{mod}f)$. It is ${\mathbb{F}}_q$-linear, and its kernel — the Berlekamp subalgebra — consists exactly of the elements that are constant in each CRT component. Its dimension is therefore $k$, the number of irreducible factors.

That gives two things at once:

1. The number of factors, for free, as $n-\mathrm{rank}(Q-I)$;
2. A way to split: for any non-constant $g$ in the kernel and any $c\in {\mathbb{F}}_q$, $\gcd (f,g-c)$ is a product of exactly those $f_i$ whose component of $g$ equals $c$ — a non-trivial factor whenever $g$ is non-constant.

Algorithm

1. Square-free part. Replace $f$ by $f/\gcd (f,f^{\prime })$ and handle repeated factors separately (square-free decomposition).
2. Build the Berlekamp matrix $Q$, whose $i$-th row is $x^{qi}\mathrm{mod}f$ expressed in the basis $1,x,\dots ,x^{n-1}$. Computing each row costs a modular exponentiation.
3. Null space of $Q-I$ by Gaussian elimination — this gives a basis $g_1=1,g_2,\dots ,g_k$ of the kernel, and $k$ is the factor count.
4. Split. For each non-trivial $g_j$ and each $c\in {\mathbb{F}}_q$, take $\gcd (f,g_j-c)$. Repeat on the pieces until $k$ factors are isolated.

Complexity

• Building $Q$: $O(n^2\log q)$ field operations
• Null space: $O(n^3)$
• Splitting: $O(q{n}^2)$ deterministic — linear in $q$, which is fine for small primes and hopeless for large ones
• Randomized splitting (Cantor-Zassenhaus style) removes the $q$ dependence

Berlekamp vs Cantor-Zassenhaus

	Berlekamp	Cantor-Zassenhaus
Type	deterministic (small $q$)	randomized (Las Vegas)
Cost	$O(n^3+q{n}^2)$	$O(n^2\log n\log q)$ expected
Best when	$q$ is small (e.g. ${\mathbb{F}}_2$)	$q$ is large
Gives factor count first	yes	no
Used in practice	small fields, coding theory	general, most CAS implementations

Uses beyond factorisation

• Root finding mod $p$. The roots of $f$ are the linear factors; computing $\gcd (f,x^p-x)$ first isolates them, then splitting finds them. This is the standard way to solve a polynomial congruence.
• Irreducibility testing. $f$ is irreducible iff the Berlekamp subalgebra has dimension 1 — one rank computation, no factorisation needed.
• Coding theory. Berlekamp designed this while working on error-correcting codes; the same author’s Berlekamp-Massey algorithm decodes BCH and Reed-Solomon codes.

Variants / Use Cases

• Cantor-Zassenhaus — the randomized standard for large fields
• Hensel lifting — lift a factorisation mod $p$ to mod $p^k$, then to $\mathbb{Z}$
• Polynomial Factorization — the topic page
• Berlekamp-Massey — same author, different problem (finding linear recurrences)