Berlekamp's algorithm

also: berlekamp matrix, nullspace

Factorization over a finite field by linear algebra: the map v to v^p - v is linear on F_p[x]/(f), and the dimension of its kernel is exactly the number of irreducible factors. That count is worth having on its own, as a check on the gcd-based algorithms that shares none of their code.

Factorization over a finite field by linear algebra rather than by GCDs. The Frobenius map is $F_{p}$ -linear on the quotient ring, so

B = {v \in F_{p} [x] / (f) ∣ v^{p} \equiv v}

is a subspace, the Berlekamp subalgebra. By the Chinese remainder theorem it is isomorphic to $F_{p}^{r}$ where $r$ is the number of distinct irreducible factors, so

r = dim ker (Q - I)

with $Q$ the matrix of $v \mapsto v^{p}$ on the basis $1, x, \dots, x^{n - 1}$ . Building it costs $n$ modular exponentiations, and the nullity comes from Gaussian elimination.

The matrix, with the identity already subtracted.

let berlekamp_matrix p f =
  let n = degree f in
  let q = Array.make_matrix n n 0 in
  for i = 0 to n - 1 do
    let row = pow_mod p (shift one i) p f in
    for j = 0 to n - 1 do q.(j).(i) <- coeff row j done;
    q.(i).(i) <- Zp.sub p q.(i).(i) 1
  done;
  q

That count is worth having even when the factors come from elsewhere. It shares no code with distinct-degree and equal-degree factorization, so running both and comparing is a genuine cross-check rather than a restatement. For large $p$ Berlekamp is the slower route, since a nontrivial kernel element still has to be turned into a split by trying $p$ values, which is why Cantor-Zassenhaus is the default.