|
In [[number theory]], the '''Berlekamp's root finding algorithm''' (, also called the ''Berlekamp-Rabin'Berlekamp–Rabin algorithm'')', is the [[Randomized algorithm|probabilistic]] method of [[Root-finding algorithm|finding roots]] of [[Polynomial|polynomials]] over a [[Finite field|field]] <math>\mathbb Z_p</math>. The method was discovered by [[Elwyn Berlekamp|Berlekamp]] in 1970<ref name=":0">{{cite journal |author = |editor= |format= |url= https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ |title= Factoring polynomials over large finite fields |type= |origyear= | agency = |edition= Mathematics of Computation |___location= |date= 1970 |year= 1970 |publisher= |at= |volume= 24 |issue= 111 |number= |pages = 713–735 |page= |series= |isbn = |issn = 00255718 |doi = 10.1090/S0025-5718-1970-0276200-X |bibcode = |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= en |quote= }}</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 |editor= |format= |url= https://epubs.siam.org/doi/10.1137/0209024 |title= Probabilistic Algorithms in Finite Fields |type= |origyear= | agency = |edition= SIAM Journal on Computing |___location= |date= 1980 |year= 1980 |publisher= |at= |volume= 9 |issue= 2 |number= |pages = 273–280 |page= |series= |isbn = |issn = 00975397 |doi = 10.1137/0209024 |bibcode = |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= |quote= }}</ref> The method was also independently discovered before Berlekamp by other researchers.<ref>{{cite book| author = Donald E Knuth | chapter = | chapter-url = | format = | url = https://www.worldcat.org/title/art-of-computer-programming-vol-2/oclc/900627019&referer=brief_results | title = The art of computer programming. Vol. 2 Vol. 2 | orig-year = | agency = | edition = |___location= |date = 1998 |publisher= |at= |volume= |issue = | pages = | page = | series = | isbn = 9780201896848| ref = }}</ref>
== History ==
The method was proposed by [[Elwyn Berlekamp]] in his work<ref name=":0" /> on polynomial factorization over finite fields. His original work lacked a formal 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 |editor= |format= |url= http://dx.doi.org/10.1090/s0025-5718-2011-02419-1 |title= On taking square roots without quadratic nonresidues over finite fields |type= |origyear= | agency = |edition= Mathematics of Computation |___location= |date= 2011 |year= 2011 |publisher= |at= |volume= 80 |issue= 275 |number= |pages = 1797–1811 |page= |series= |isbn = |issn = 00255718 |doi = 10.1090/s0025-5718-2011-02419-1 |bibcode = |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= |quote= }}</ref> for finding square roots in <math>\mathbb Z_p</math><ref>{{cite journal |author = R. Peralta |editor= |format= |url= https://ieeexplore.ieee.org/document/1057236 |title= A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.) |type= |origyear= | agency = |edition= IEEE Transactions on Information Theory |___location= |date= 1986 |year= 1986 |publisher= |at= |volume= 32 |issue= 6 |number= |pages = 846–847 |page= |series= |isbn = |issn = 00189448 |doi = 10.1109/TIT.1986.1057236 |bibcode = |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= |quote= }}</ref>. In 2000 Peralta's method was generalized for cubic equations.<ref>{{cite journal |author = C Padró, G Sáez |editor= |format= |url= http://dx.doi.org/10.1016/s0893-9659(02)00031-9 |title= Taking cube roots in Zm |type= |origyear= | agency = |edition= Applied Mathematics Letters |___location= |date= 2002 |year= 2002 |publisher= |at= |volume= 15 |issue= 6 |number= |pages = 703–708 |page= |series= |isbn = |issn = 08939659 |doi = 10.1016/s0893-9659(02)00031-9 |bibcode = |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= |quote= }}</ref>
== Statement ==
Let <math>p</math> be an odd prime number. Consider the polynomial <math display="inline">f(x) = a_0 + a_1 x + \dotscdots + a_n x^n</math> over field <math>\mathbb Z_p</math> of remainders modulo <math>p</math>. The algorithm should find all <math>\lambda_1, \dotsldots, \lambda_k</math> such that <math display="inline">f(\lambda_i)\equiv 0 \pmod p</math> for every possible <math>i</math>.<ref name=":1" /><ref name=":2">{{cite book| author = Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone | chapter = | chapter-url = | format = | url = https://www.springer.com/gp/book/9780792392828 | title = Applications of Finite Fields | orig-year = | agency = | edition = |___location= |date = 1993 |publisher= Springer US |at= |volume= |issue = | pages = | page = | series = The Springer International Series in Engineering and Computer Science | isbn = 9780792392828| ref = }}</ref>
== Algorithm ==
=== Randomization ===
Let <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\dotscdots(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) \dotscdots (x-\lambda_n-z)</math> where <math>z</math> is some any element of <math>\mathbb Z_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 Z_p</math> elements ===
# Explicitly calculate coefficients of <math>f_z(x) = f(x-z)</math>,
# Calculate remainders of <math display="inline">x,x^2, x^{2^2},x^{2^3}, x^{2^4}, \dotsldots, x^{2^{\lfloor \log_2 p \rfloor}}</math> modulo <math>f_z(x)</math> by squaring the current polynomial and taking remainder modulo <math>f_z(x)</math>,
# Using [[exponentiation by squaring]] and polynomials calculated on the previous steps calculate the remainder of <math display="inline">x^{(p-1)/2}</math> modulo <math display="inline">f_z(x)</math>,
# If <math display="inline">x^{(p-1)/2} \not \equiv \pm 1 \pmod{f_z(x)}</math> then <math>\gcd</math> mentioned above provide a non-trivial factorization of <math>f_z(x)</math>,
== Correctness proof ==
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, \dotsldots, z+\lambda_n</math> are quadratic residues or non-residues simultaneously. According to [[theory of cyclotomy]],<ref>{{cite book| author = Marshall Hall | chapter = | chapter-url = | format = | url = https://books.google.ru/books?hl=en&lr=&id=__JCiiCfu2EC&oi=fnd&pg=PA1&dq=Combinatorial+Theory+hall&ots=WeNDZ7uCSM&sig=a6JwSPPen2C2EysEnkSTXpUNaxM&redir_esc=y#v=onepage&q=Combinatorial%20Theory%20hall&f=false | title = Combinatorial Theory | orig-year = | agency = | edition = |___location= |date = 1998 |publisher= John Wiley & Sons |at= |volume= |issue = | pages = | page = | series = | isbn = 9780471315186| ref = }}</ref> the probability of such an event for the case when <math>\lambda_1, \dotsldots, \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 dinstinct values in <math>\lambda_1, \dotsldots, \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 ==
| 