Berlekamp's algorithm: Difference between revisions

Revision as of 16:00, 23 April 2023

Latest revision as of 20:57, 28 July 2025

(4 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Method in computational algebra}}

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

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 book | title=Theory of Computation - Dexter Kozen | websitepublisher=Springer | url=https://www.springer.com/gp/book/9781846282973 | access-date=2020-09-19}}</ref>

==Applications==

Line 87 ⟶ 88:

[[Category:Computer algebra]]

[[Category:Finite fields]]

[[Category:PolynomialsPolynomial factorization algorithms]]