Berlekamp's algorithm: Difference between revisions

Revision as of 16:34, 28 February 2013

Revision as of 14:00, 5 March 2013

Line 16:

In general, not every GCD in the above product will be a non-trivial factor of <math>f(x)</math>, but some are, providing the factors we seek.

Berlekamp's algorithm finds polynomials <math>g(x)</math> suitable for use with the above result by computing a basis for the Berlekamp subalgebra. This is achieved via the observation that Berlekamp subalgebra is in fact the [[null spacekernel]] of a certain <math>(n+1) \times (n+1)</math> matrix over <math>\mathbb{F}_q</math>, which is derived from the so-called Berlekamp matrix of the polynomial, denoted <math>\mathcal{Q}</math>. If <math>\mathcal{Q}=[q_{i,j}]</math> then <math>q_{i,j}</math> is the coefficient of the <math>j</math>-th power term in the reduction of <math>x^{iq}</math> modulo <math>f(x)</math>, i.e.:

:<math>x^{iq} \equiv q_{i,n}x^n + q_{i,n-1}x^{n-1} + \ldots + q_{i,0} \pmod{f(x)}.\,</math>