Berlekamp–Rabin algorithm: Difference between revisions

Revision as of 06:28, 13 May 2024

Latest revision as of 20:25, 19 June 2025

(6 intermediate revisions by 5 users not shown)

Line 1:

{{short description|Method in number theory}}

[[File:Elwyn_R_Berlekamp_2005.jpg|thumb|right|Elwyn R. Berlekamp at conference on Combinatorial Game Theory at [[Banff International Research Station]]]]

In [[number theory]], '''Berlekamp's root finding algorithm''', also called the '''Berlekamp–Rabin algorithm''', is the [[Randomized algorithm|probabilistic]] method of [[Root-finding algorithm|finding roots]] of [[Polynomial|polynomials]] over the [[Finite field|field]] <math>\mathbb F_p</math> with <math>p</math> elements. The method was discovered by [[Elwyn Berlekamp]] in 1970<ref name=":0">{{cite journal |url= https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ |title= Factoring polynomials over large finite fields |journal= Mathematics of Computation |year= 1970 |volume= 24 |issue= 111 |pages = 713–735 |issn = 0025-5718 |doi = 10.1090/S0025-5718-1970-0276200-X |language= en |last1= Berlekamp|first1= E. R.|doi-access= free|url-access= subscription }}</ref> as an auxiliary to the [[Berlekamp's algorithm|algorithm]] for polynomial factorization over finite fields. The algorithm was later modified by [[Michael O. Rabin|Rabin]] for arbitrary finite fields in 1979.<ref name=":1">{{cite journal |author = M. Rabin |title= Probabilistic Algorithms in Finite Fields |journal= SIAM Journal on Computing |year= 1980 |volume= 9 |issue= 2 |pages = 273–280 |issn = 0097-5397 |doi = 10.1137/0209024 |citeseerx= 10.1.1.17.5653 }}</ref> The method was also independently discovered before Berlekamp by other researchers.<ref>{{cite book| author = Donald E Knuth | author-link = Donald E Knuth | title = The art of computer programming. Vol. 2 Vol. 2 |date = 1998 | publisher = Addison-Wesley | isbn = 978-0201896848| oclc = 900627019 }}</ref>

Elwyn Berlekamp]]

In [[number theory]], '''Berlekamp's root finding algorithm''', also called the '''Berlekamp–Rabin algorithm''', is the [[Randomized algorithm|probabilistic]] method of [[Root-finding algorithm|finding roots]] of [[Polynomial|polynomials]] over the [[Finite field|field]] <math>\mathbb F_p</math> with <math>p</math> elements. The method was discovered by [[Elwyn Berlekamp]] in 1970<ref name=":0">{{cite journal |url= https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ |title= Factoring polynomials over large finite fields |journal= Mathematics of Computation |year= 1970 |volume= 24 |issue= 111 |pages = 713–735 |issn = 0025-5718 |doi = 10.1090/S0025-5718-1970-0276200-X |language= en |last1= Berlekamp|first1= E. R.|doi-access= free}}</ref> as an auxiliary to the [[Berlekamp's algorithm|algorithm]] for polynomial factorization over finite fields. The algorithm was later modified by [[Michael O. Rabin|Rabin]] for arbitrary finite fields in 1979.<ref name=":1">{{cite journal |author = M. Rabin |title= Probabilistic Algorithms in Finite Fields |journal= SIAM Journal on Computing |year= 1980 |volume= 9 |issue= 2 |pages = 273–280 |issn = 0097-5397 |doi = 10.1137/0209024 |citeseerx= 10.1.1.17.5653 }}</ref> The method was also independently discovered before Berlekamp by other researchers.<ref>{{cite book| author = Donald E Knuth | author-link = Donald E Knuth | title = The art of computer programming. Vol. 2 Vol. 2 |date = 1998 | isbn = 978-0201896848| oclc = 900627019 }}</ref>

== History ==

The method was proposed by [[Elwyn Berlekamp]] in his 1970 work<ref name=":0" /> on polynomial factorization over finite fields. His original work lacked a formal [[Correctness (computer science)|correctness]] proof<ref name=":1" /> and was later refined and modified for arbitrary finite fields by [[Michael O. Rabin|Michael Rabin]].<ref name=":1" /> In 1986 René Peralta proposed a similar [[algorithm]]<ref>{{cite journal |author = Tsz-Wo Sze |title= On taking square roots without quadratic nonresidues over finite fields |journal= Mathematics of Computation|year= 2011 |volume= 80 |issue= 275 |pages = 1797–1811 |issn = 0025-5718 |doi = 10.1090/s0025-5718-2011-02419-1 |arxiv =0812.2591 |s2cid= 10249895 }}</ref> for finding square roots in <math>\mathbb F_p</math>.<ref>{{cite journal |author = R. Peralta |title= A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.) |journal= IEEE Transactions on Information Theory |date=November 1986 |volume= 32 |issue= 6 |pages = 846–847 |issn = 0018-9448 |doi = 10.1109/TIT.1986.1057236 }}</ref> In 2000 Peralta's method was generalized for [[Cubic equation|cubic equations]].<ref>{{cite journal |author = C Padró, G Sáez |title= Taking cube roots in Zm |journal= Applied Mathematics Letters |date=August 2002 |volume= 15 |issue= 6 |pages = 703–708 |issn = 0893-9659 |doi = 10.1016/s0893-9659(02)00031-9 |doi-access= }}</ref>

== Statement of problem==

Line 13 ⟶ 12:

=== Randomization ===

Let <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. Finding all roots of this polynomial is equivalent to finding its factorization into linear factors. To find such factorization it is sufficient to split the polynomial into any two non-trivial divisors and factorize them recursively. To do this, consider the polynomial <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math> where <math>z</math> is some any element of <math>\mathbb F_p</math>. If one can represent this polynomial as the product <math>f_z(x)=p_0(x)p_1(x)</math> then in terms of the initial polynomial it means that <math>f(x) =p_0(x+z)p_1(x+z)</math>, which provides needed factorization of <math>f(x)</math>.<ref name=":0" /><ref name=":2" />

=== Classification of <math>\mathbb F_p</math> elements ===

Line 54 ⟶ 53:

== Correctness proof ==

The algorithm finds [[factorization]] of <math>f_z(x)</math> in all cases except for ones when all numbers <math>z+\lambda_1, z+\lambda_2, \ldots, z+\lambda_n</math> are quadratic residues or non-residues simultaneously. According to [[theory of cyclotomy]],<ref>{{cite book| author = Marshall Hall | url = https://books.google.com/books?id=__JCiiCfu2EC&q=Combinatorial+Theory+hall&pg=PA1 | title = Combinatorial Theory |date = 1998 |publisher= John Wiley & Sons | isbn = 9780471315186}}</ref> the probability of such an event for the case when <math>\lambda_1, \ldots, \lambda_n</math> are all residues or non-residues simultaneously (that is, when <math>z=0</math> would fail) may be estimated as <math>2^{-k}</math> where <math>k</math> is the number of distinct values in <math>\lambda_1, \ldots, \lambda_n</math>.<ref name=":0" /> In this way even for the worst case of <math>k=1</math> and <math>f(x)=(x-\lambda)^n</math>, the probability of error may be estimated as <math>1/2</math> and for modular square root case error probability is at most <math>1/4</math>.

== Complexity ==