Berlekamp's algorithm: Difference between revisions

Revision as of 03:23, 18 May 2021

Latest revision as of 20:57, 28 July 2025

(10 intermediate revisions by 7 users not shown)

Line 1:

{{Short description|Method in computational algebra}}

{{for|the algorithm dealing with LFSRs|Berlekamp–Massey algorithm}}

Line 34 ⟶ 35:

==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 <math display="inline">p</math>, 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.

Moreover, we can use the fact that the Frobenius automorphism is <math display = "inline"> \mathbb{F}_p </math>-linear to calculate the fixed set. That is, we note that <math display = "inline"> \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) </math> is a <math display = "inline"> \mathbb{F}_p </math>-subspace, and an explicit basis for it can be calculated in the polynomial ring <math display = "inline"> \mathbb{F}_p[x,y]/(f,g) </math> by computing <math display = "inline"> (x^i y^j)^p </math> and establishing the linear equations on the coefficients of <math display = "inline"> x,y </math> polynomials that are satisfied iff it is fixed by Frobenius. We note that at this point we have an efficiently computable irreducibility criterion, and the remaining analysis shows how to use this to find factors.

Line 45 ⟶ 46:

* For the case of large primes, which are necessarily odd, one can exploit the fact that a random nonzero element of <math display = "inline"> \mathbb{F}_p^* </math> is a square with probability <math display = "inline"> 1/2 </math>, and that the map <math display = "inline"> x \to x^{ \frac{ p -1}{2}} </math> maps the set of non-zero squares to <math display = "inline"> 1 </math>, and the set of non-squares to <math display = "inline"> -1 </math>. Thus, if we take a random element <math display = "inline"> g \in \text{Fix}_p( \mathbb{F}_q[x]/f(x)) </math>, then with good probability <math display = "inline"> g^{ \frac{ p - 1}{2}} - 1 </math> will have a non-trivial factor in common with <math display = "inline"> f(x) </math>.

For further details one can consult.<ref name="Springer">{{cite webbook | title=Theory of Computation - Dexter Kozen | websitepublisher=Springer | url=https://www.springer.com/gp/book/9781846282973 | access-date=2020-09-19}}</ref>

==Applications==

Line 68 ⟶ 69:

|pages=1853–1859

|year=1967

|issue=8

|mr=0219231

|doi=10.1002/j.1538-7305.1967.tb03174.x}} [http://www.alcatel-lucent.com/bstj/vol46-1967/articles/bstj46-8-1853.pdf BSTJ] Later republished in: {{Cite book |first=Elwyn R. |last=Berlekamp |title=Algebraic Coding Theory |publisher=McGraw Hill |year=1968 |isbn=0-89412-063-8 }}

Line 86 ⟶ 88:

[[Category:Computer algebra]]

[[Category:Finite fields]]

[[Category:Polynomial factorization algorithms]]