Berlekamp algorithm

from Wikipedia, the free encyclopedia

In computer algebra , a branch of mathematics , the Berlekamp algorithm is a method for factoring 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 factorization algorithm until the Cantor-Zassenhaus algorithm , a probabilistic variant of the Berlekamp algorithm from 1981, was developed.

background

We are looking for a factorization of with into irreducible factors where the size is unknown. In particular, it can also apply, namely when is irreducible . Without loss of generality, it can be assumed that it is square-free , because square-free polynomials fulfill the property and a real divisor is found in this way for non-square-free polynomials. ( here denotes the formal derivative with respect to x and the greatest common factor .)

To determine this, one uses a polynomial which is easier to factorize and which is divided by, because then applies

Since a finite field is, can the identity of the through receives replace .

In order to actually divide by, one looks for one which fulfills the congruence .

One can now prove that all eigenvectors of a certain matrix with eigenvalue 1 each yield one, where they are given by the congruences:

.

Because then the congruence applies:

.

So you determine all eigenvectors of and then receives by all and for all eigenvectors to be calculated. On the one hand, you can omit the trivial eigenvector and, on the other hand, end the calculations when you have found various factors.

algorithm

The algorithm can be summarized as follows:

  • One calculates by reducing for each .
  • One determines a basis of the eigenspace of for eigenvalue 1.
  • Until all the factors of have been determined, calculate for everyone and for everyone
.

application

An important application of the Berlekamp algorithm is the computation of the discrete logarithm over a finite field with a prime number and , which is of great importance in public key cryptography . In a finite field, the fastest method of computing the discrete logarithm is the Index Calculus algorithm , which factorizes elements of the body. Since it is isomorphic to a polynomial ring over , factored according to an irreducible polynomial of degree , the factorization of the body elements in the factorization of polynomials in a polynomial ring over , factored according to an irreducible polynomial of degree . This can then be carried out with the Berlekamp algorithm.

See also

literature

  • Atilla Pethö: Algebraic Algorithms . Ed .: Michael Pohst. Vieweg, 1999, ISBN 978-3-528-06598-0 , pp. 183 .
  • Michael Kaplan: Computer Algebra . Springer, 2005, ISBN 3-540-21379-1 , pp. 239 .
  • Elwyn R. Berlekamp: Factoring Polynomials Over Finite Fields . In: Bell System Technical Journal , Volume 46, 1967, pp. 1853-1859 or in: Elwyn R. Berlekamp: Algebraic Coding Theory . Mc-Graw Hill, 1968.