Content deleted Content added
Rcampbell1 (talk | contribs) |
|||
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 space]] 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>
Line 28:
:<math>g = (g_0, g_1, \ldots, g_n).\,</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]].
| |||