Berlekamp's algorithm

In computer algebra, a branch of mathematics, the Berlekamp algorithm is a method of factorization of polynomials over a finite field, which was developed in 1967 by Elwyn Berlekamp. It is implemented in most computer algebra systems and was the leading factoring algorithm to the development of the Cantor - Zassenhaus algorithm, a probabilistic variant of the Berlekamp algorithm from the year 1981.

Background

Wanted is a factorization into irreducible factors of with the size is unknown. In particular, can also apply, namely when is irreducible. Here, one can assume without loss of generality that is square-free, because square-free polynomials satisfy the property and not square-free polynomials in this way already a proper divisor is found. ( Refers to the formal derivative with respect to x and the greatest common divisor here.)

To determine, use is made of a more easily factorized polynomial is divided by, for then applies

Since a finite field is, one can replace in the identity and obtains.

Because is divisible by, so we investigated that satisfy the congruence.

One can now prove that all these eigenvectors of a matrix corresponding to the eigenvalue 1, which are given by the congruences:

Because then the following applies:

So you determined all eigenvectors of and then receives, by calculating for all and for all eigenvectors. It can, on the one omit the trivial eigenvector and on the other end the calculations if you have several factors have been found.

Algorithm

The algorithm can therefore be summarized as follows:

• Calculating, by reducing for each.
• Determine a basis of the eigenspace of the eigenvalue 1
• As long as not all factors are determined by, compute for all and for all

Application

An important application of the Berlekamp algorithm is the computation of the discrete logarithm over a finite field of prime and what is of great importance in the Public Key Cryptography. In a finite field is the fastest method for calculating the discrete logarithm of the index - calculus algorithm, are factorized in the body elements. Since is isomorphic to a polynomial ring over, factored by an irreducible polynomial of degree, equivalent to the factorization of the body elements in the factorization of polynomials in a polynomial ring over, factored by an irreducible polynomial of degree. This can then be performed with the Berlekamp algorithm.