Berlekamp's algorithm

In mathematics, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials over finite fields (also known as Galois fields). The algorithm consists mainly of matrix reduction and polynomial GCD computations. It was invented by Elwyn Berlekamp in 1967. It was the dominant algorithm for solving the problem until the Cantor–Zassenhaus algorithm of 1981. It is currently implemented in many well-known computer algebra systems.

Berlekamp's algorithm takes as input a square-free polynomial ${\displaystyle f(x)}$ (i.e. one with no repeated factors) of degree ${\displaystyle n}$ with coefficients in a finite field ${\displaystyle \mathbb {F} _{q}}$ and gives as output a polynomial ${\displaystyle g(x)}$ with coefficients in the same field such that ${\displaystyle g(x)}$ divides ${\displaystyle f(x)}$. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of ${\displaystyle f(x)}$ into powers of irreducible polynomials (recalling that the ring of polynomials over a finite field is a unique factorization domain).

...
Wikipedia