Content deleted Content added
Luke Maurits (talk | contribs) m Fixed link to Cantor-Zassenhaus algorithm |
Luke Maurits (talk | contribs) m Fixed link to Cantor-Zassenhaus algorithm |
||
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|polynomials]] over [[finite field|finite fields]] (aka [[galois field|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|computer algebra systems]], including [[PARI-GP_computer_algebra_system|PARI-GP]].
==Overview==
| |||