Berlekamp's algorithm: Difference between revisions

Revision as of 03:23, 18 May 2021

Revision as of 00:10, 26 September 2021

Line 34:

==Conceptual algebraic explanation==

With some abstract algebra, the idea behind Berlekamp'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.

Now, suppose that <math display = "inline"> f(x) = f_1(x) \ldots f_n(x) </math> is the factorization into irreducibles. Then we have a ring isomorphism, <math display = "inline"> \sigma: \mathbb{F}_q[x]/(f(x)) \to \prod_i \mathbb{F}_q[x]/(f_i(x)) </math>, given by the Chinese remainder theorem. The crucial observation is that the Frobenius automorphism <math display = "inline"> x \to x^p </math> commutes with <math display = "inline"> \sigma </math>, so that if we denote <math display = "inline"> \text{Fix}_p(R) = \{ f \in R : f^p = f \} </math>, then <math display = "inline"> \sigma </math> restricts to an isomorphism <math display = "inline"> \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) \to \prod_{i = 1}^n \text{Fix}_p( \mathbb{F}_q[x]/(f_i(x)) ) </math>. By finite field theory, <math display = "inline"> \text{Fix}_p( \mathbb{F}_q[x]/(f_i(x)) </math> is always the prime subfield of that field extension. Thus, <math display = "inline"> \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) </math> has <math display = "inline"> p </math> elements if and only if <math display = "inline"> f(x) </math> is irreducible.