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 is currently implemented in many well-known computer algebra systems.
Berlekamp's algorithm takes as input a square-free polynomial
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).
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
it contains satisfy In general, not every GCD in the above product will be a non-trivial factor of
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 kernel of a certain
, which is derived from the so-called Berlekamp matrix of the polynomial, denoted
identity matrix), i.e. if and only if it is in the null space of
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
We then need to successively compute GCDs of the form above until we find a non-trivial factor.
With some abstract algebra, the idea behind Berlekamp's algorithm becomes conceptually clear.
is square free, by taking all possible pth roots and then computing the gcd with its derivative.
The crucial observation is that the Frobenius automorphism
is always the prime subfield of that field extension.
-subspace, and an explicit basis for it can be calculated in the polynomial ring
and establishing the linear equations on the coefficients of
polynomials that are satisfied iff it is fixed by Frobenius.
We note that at this point we have an efficiently computable irreducibility criterion, and the remaining analysis shows how to use this to find factors.
The algorithm now breaks down into two cases: For further details one can consult.
[1] One important application of Berlekamp's algorithm is in computing discrete logarithms over finite fields
Computing discrete logarithms is an important problem in public key cryptography and error-control coding.
For a finite field, the fastest known method is the index calculus method, which involves the factorisation of field elements.
, reduced modulo an irreducible polynomial of degree
- then this is simply polynomial factorisation, as provided by Berlekamp's algorithm.
Berlekamp's algorithm may be accessed in the PARI/GP package using the factormod command, and the WolframAlpha [1] website.