Berlekamp's algorithm

Summary

Berlekamp's algorithm factors square-free polynomials over a finite field by linear algebra. It finds the polynomials $g$ of degree less than $\deg f$ with $g^q \equiv g$ modulo $f$. They form a vector space whose dimension is the number of irreducible factors of $f$. Greatest common divisors of $f$ with $g - s$ for constants $s$ then split $f$. It is deterministic, and it was the main method of factorization over finite fields until the randomised Cantor–Zassenhaus algorithm of 1981.