 Berlekamp's algorithm takes as input a square-free polynomial formula_1 (i.e.one with no repeated factors) of degree formula_2 with coefficients in a finite field formula_3 and gives as output a polynomial formula_4 with coefficients in the same field such that formula_4 divides formula_1.The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of formula_1 into powers of irreducible polynomials (recalling that the ring of polynomials over a finite field is a unique factorization domain).