Berlekamp's algorithm: Difference between revisions

Revision as of 21:36, 23 September 2014

Revision as of 08:30, 15 November 2015

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 [[kernel (linear algebra)|kernel]] 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-1}x^{n-1} + q_{i,n-12}x^{n-12} + \ldots + q_{i,0} \pmod{f(x)}.\,</math>

With a certain polynomial <math>g(x) \in R</math>, say:

:<math>g(x) = g_nxg_{n-1}x^{n-1}+g_{n-12}x^{n-12} + \ldots + g_0,\,</math>

we may associate the row vector:

:<math>g = (g_0, g_1, \ldots, g_ng_{n-1}).\,</math>

It is relatively straightforward to see that the row vector <math>g\mathcal{Q}</math> corresponds, in the same way, to the reduction of <math>g(x)^q</math> modulo <math>f(x)</math>. Consequently a polynomial <math>g(x) \in R</math> is in the Berlekamp subalgebra if and only if <math>g(\mathcal{Q}-I)=0</math> (where <math>I</math> is the <math>(n+1) \times (n+1)</math> [[identity matrix]]), i.e. if and only if it is in the null space of <math>\mathcal{Q}-I</math>.

By computing the matrix <math>\mathcal{Q}-I</math> and reducing it to [[reduced row echelon form]] and then easily reading off a basis for the null space, we may find a basis for the Berlekamp subalgebra and hence construct polynomials <math>g(x)</math> in it. We then need to successively compute GCDs of the form above until we find a non-trivial factor. Since the ring of polynomials over a field is a [[Euclidean ___domain]], we may compute these GCDs using the [[Euclidean algorithm]].