Berlekamp's algorithm: Difference between revisions

Revision as of 03:25, 22 July 2006

Revision as of 04:05, 14 August 2006

Line 4:

==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]] (recalling that the [[ring_(mathematics)|ring]] of polynomials over a finite field is a [[unique factorisationfactorization ___domain]]).

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