Berlekamp's algorithm: Difference between revisions

Revision as of 09:16, 18 September 2006

Revision as of 13:34, 2 April 2007

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 (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]]s, including [[PARI-GP computer algebra system|PARI-/GP]].

==Overview==

Line 36:

==Implementation in Computer Algebra Systems==

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

==See also==