{{dablinkfor|This article discusses an algorithm for factorisation of polynomials over finite fields. For the algorithm dealing with LFSRs see [[Berlekamp-Massey|Berlekamp–Massey algorithm]].}}
In [[mathematics]], particularly [[computer algebra|computational algebra]], '''Berlekamp's algorithm''' is a well-known method for factorising [[polynomialPolynomial factorization|factoring polynomials]]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-ZassenhausCantor–Zassenhaus algorithm]] of 1981. It is currently implemented in many well-known [[computer algebra system]]s, including [[PARI/GP]].
==Overview==
Line 37:
==Implementation in Computer Algebra Systems==
Berlekamp's algorithm may be accessed in the PARI/GP package using the [http://pari.math.u-bordeaux.fr/dochtml/html.stable/Arithmetic_functions.html#factormod factormod] command.
