Content deleted Content added
Lorenzo.Najt (talk | contribs) m →Conceptual Algebraic Explanation: fixed typo |
section header |
||
Line 32:
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]].
==Conceptual
With some abstract algebra, the idea behind Berlkemap's algorithm becomes conceptually clear. We represent a finite field <math display = "inline"> \mathbb{F}_q[x] </math>, where <math display="inline"> q = p^m </math> for some prime p, as <math display = "inline"> \mathbb{F}_p[y]/(g(y)) </math>. We can assume that <math display = "inline"> f(x) \in \mathbb{F}_q[x] </math> is square free, by taking all possible pth roots and then computing the gcd with its derivative.
| |||