Berlekamp's algorithm: Difference between revisions

Revision as of 04:05, 14 August 2006

Revision as of 19:12, 15 August 2006

Line 1:

{{dablink|This article discusses an algorithm for factorisation of polynomials over finite fields. For the algorithm dealing with LFSRs see [[Berlekamp-Massey algorithm]].}}

In [[mathematics]], particularly [[computer algebra|computational algebra]], Berlekamp's algorithm is a well-known method for factorising [[polynomial]]s over [[finite field]]s (also known as ''Galois fields''). The algorithm consists mainly of [[matrix_matrix (mathematics)|matrix]] reduction and polynomial [[greatest common divisor|GCD]] computations. It was invented by [[Elwyn Berlekamp]] in 1967. It was the dominant algorithm for solving the problem until the [[Cantor-Zassenhaus Algorithm|Cantor-Zassenhaus algorithm]] of 1981. It is currently implemented in many well-known [[computer algebra system|computer algebra systems]]s, including [[PARI-GP_computer_algebra_systemGP computer algebra system|PARI-GP]].

==Overview==

Berlekamp's algorithm takes as input a square-free polynomial <math>f(x)</math> (i.e. one with no repeated factors) of degree <math>n</math> with coefficients in a finite field <math>\mathbb{F}_q</math> and gives as output a polynomial <math>g(x)</math> with coefficients in the same field such that <math>g(x)</math> divides <math>f(x)</math>. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of <math>f(x)</math> into powers of [[irreducible polynomial|irreducible polynomials]]s (recalling that the [[ring_ring (mathematics)|ring]] of polynomials over a finite field is a [[unique factorization ___domain]]).

All possible factors of <math>f(x)</math> are contained within the [[factor ring]]

Line 33:

==Applications==

One important application of Berlekamp's algorithm is in computing [[discrete logarithm|discrete logarithms]]s over finite fields of prime-power order. Computing discrete logarithms is an important problem in [[public key cryptography]]. For a field of prime-power order, the fastest known method is the [[index calculus|index calculus method]], which involves the factorisation of field elements. If we represent the prime-power order field in the usual way - that is, as polynomials over the prime order base field, reduced modulo an irreducible polynomial of appropriate degree - then this is simply polynomial factorisation, as provided by Berlekamp's algorithm.

==Implementation in Computer Algebra Systems==

Berlekamp's algorithm may be accessed in the GP-PARI package using the [http://pari.math.u-bordeaux.fr/dochtml/html.stable/Arithmetic_functions.html#factormod factormod] command.

==See Alsoalso==

*[[Polynomial factorization|Polynomial factorisation]]

*[[Cantor-Zassenhaus algorithm]]