Berlekamp's Algorithm - Overview

Overview

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

All possible factors of are contained within the factor ring

The algorithm focuses on polynomials which satisfy the congruence:

These polynomials form a subalgebra of R (which can be considered as an -dimensional vector space over ), called the Berlekamp subalgebra. The Berlekamp subalgebra is of interest because the polynomials it contains satisfy

In general, not every GCD in the above product will be a non-trivial factor of, but some are, providing the factors we seek.

Berlekamp's algorithm finds polynomials suitable for use with the above result by computing a basis for the Berlekamp subalgebra. This is achieved via the observation that Berlekamp subalgebra is in fact the null space of a certain matrix over, which is derived from the so-called Berlekamp matrix of the polynomial, denoted . If then is the coefficient of the -th power term in the reduction of modulo, i.e.:

With a certain polynomial, say:

we may associate the row vector:

It is relatively straightforward to see that the row vector corresponds, in the same way, to the reduction of modulo . Consequently a polynomial is in the Berlekamp subalgebra if and only if (where is the identity matrix), i.e. if and only if it is in the null space of .

By computing the matrix and reducing it to reduced row echelon form and then easily reading off a basis for the null space, we may find a basis for the Berlekamp subalgebra and hence construct polynomials in it. We then need to successively compute GCDs of the form above until we find a non-trivial factor. Since the ring of polynomials over a field is a Euclidean domain, we may compute these GCDs using the Euclidean algorithm.