Berlekamp Algorithm

An algorithm to factor polynomials over finite fields that uses linear algebra to find the Berlekamp subalgebra: one computes a basis of polynomials fixed by the Frobenius map (x → x^q) modulo the polynomial and extracts nontrivial factors via gcds with linear combinations of basis elements.