Berlekamp–Rabin algorithm: Difference between revisions

Revision as of 22:37, 27 July 2019

Revision as of 23:07, 27 July 2019

Line 1:

In [[number theory]], '''Berlekamp's root finding algorithm''' (also ''Berlekamp-Rabin algorithm'') is the [[Randomized algorithm|probabilistic]] method of [[Root-finding algorithm|finding roots]] of [[Polynomial|polynomials]] over [[Finite field|field]] <math>\mathbb Z_p</math>. The method was discovered by [[Elwyn Berlekamp|Berlekamp]] in 1970<ref name=":0">{{Статьяcite journal |author =E. R. Berlekamp|yeareditor=1970 |doiformat=10 |url= https://www.1090ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ |issntitle=00255718 Factoring polynomials over large finite fields |выпускtype=111 |языкorigyear=en |страницы agency =713–735 |изданиеedition= Mathematics of Computation |заглавие___location=Factoring polynomials over|date= large finite1970 fields|ссылкаyear=https://www.ams.org/mcom/ 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 =24 |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= en |quote= }}</ref> as an auxiliary to the [[Berlekamp's algorithm|algorithm]] for polynomial factorization over finite field. The algorithm was later modified by [[Michael O. Rabin|Rabin]] for arbitrary finite field in 1979<ref name=":1">{{Статьяcite journal |авторauthor = M. Rabin |годeditor=1980 |doiformat= |url= https://epubs.siam.org/doi/10.1137/0209024 |issntitle=00975397 Probabilistic Algorithms in Finite Fields |выпускtype=2 |страницыorigyear=273–280 |издание agency = |edition= SIAM Journal on Computing |заглавие___location=Probabilistic Algorithms in|date= Finite Fields1980 |ссылкаyear=https://epubs.siam.org/ 1980 |publisher= |at= |volume= 9 |issue= 2 |number= |pages = 273–280 |page= |series= |isbn = |issn = 00975397 |doi/ = 10.1137/0209024 |томbibcode =9 |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= |quote= }}</ref>. The method was also independently discovered before Berlekamp by some other researchers<ref>{{Книгаcite book|автор author = Donald E Knuth |год chapter =1998 |isbn=9780201896848|заглавие=The artchapter-url of= computer| programming.format Vol.= 2| Vol.url 2|ссылка= 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. Original work lacked 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 similar algorithm<ref>{{Статьяcite journal |авторauthor = Tsz-Wo Sze |годeditor=2011 |doiformat= |url= http://dx.doi.org/10.1090/s0025-5718-2011-02419-1 |issntitle=00255718 On taking square roots without quadratic nonresidues over finite fields |выпускtype=275 |страницыorigyear=1797–1811 |издание agency = |edition= Mathematics of Computation |заглавие___location=On taking square|date= roots without2011 quadratic|year= nonresidues2011 over|publisher= finite fields|ссылкаat=http://dx. |volume= 80 |issue= 275 |number= |pages = 1797–1811 |page= |series= |isbn = |issn = 00255718 |doi.org/ = 10.1090/s0025-5718-2011-02419-1 |томbibcode =80 |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=1986 |doiformat=10.1109 |url= https:/TIT/ieeexplore.1986ieee.org/document/1057236|issn=00189448|выпуск=6|страницы=846–847|издание=IEEE Transactions on Information Theory|заглавиеtitle= A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.) |ссылкаtype=https: |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//ieeexploreTIT.ieee1986.org/document/1057236 |томbibcode =32 |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=2002 |doiformat= |url= http://dx.doi.org/10.1016/s0893-9659(02)00031-9 |issntitle=08939659 Taking cube roots in Zm |выпускtype=6 |страницыorigyear=703–708 |издание agency = |edition= Applied Mathematics Letters |заглавие___location=Taking cube roots|date= in Zm2002 |ссылкаyear=http://dx. 2002 |publisher= |at= |volume= 15 |issue= 6 |number= |pages = 703–708 |page= |series= |isbn = |issn = 08939659 |doi.org/ = 10.1016/s0893-9659(02)00031-9 |томbibcode =15 |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= |quote= }}</ref>.

== Statement ==

Let <math>p</math> be the odd prime number. Consider polynomial <math display="inline">f(x) = a_0 + a_1 x + \dots + a_n x^n</math> over field <math>\mathbb Z_p</math> of remainders modulo <math>p</math>. One have to find all <math>\lambda_1, \dots, \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 =1993 |isbn 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 |заглавие=Applications ofisbn Finite= Fields9780792392828|ссылка ref =https://www.springer.com/gp/book/9780792392828 }}</ref>.

== Algorithm ==

Line 51:

== 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, \dots, z+\lambda_n</math> are quadratic residues or non-residues simultaneously. According to [[theory of cyclotomy]]<ref>{{Книгаcite book|автор author = Marshall Hall |год chapter =1998 |isbn=9780471315186|страниц=464|издательство=John Wileychapter-url &= Sons|заглавие format =Combinatorial Theory|ссылка 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> probability of such event for the case when <math>\lambda_1, \dots, \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 different values among <math>\lambda_1, \dots, \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> 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 ==

Line 61:

# Taking <math>\gcd</math> of two polynomials via [[Euclidean algorithm]] works in <math>O(n^2)</math>.

Thus the whole procedure may be done in <math>O(n^2 \log p)</math>. Using [[fast Fourier transform]] and Half-GCD algorithm<ref>{{Книгаcite book|автор author = Aho, Alfred V. |год chapter =1974 |isbn chapter-url =0201000296 |издательство format =Addison-Wesley Pub| url = http://worldcat.org/oclc/1147299 Co|заглавие title = The design and analysis of computer algorithms |ссылка orig-year =http://worldcat | agency = | edition = |___location= |date = 1974 |publisher= Addison-Wesley Pub.org/oclc/1147299 Co |at= |volume= |issue = | pages = | page = | series = | isbn = 0201000296| ref = }}</ref> complexity may be improved to <math>O(n \log n \log pn)</math>. For modular square root case the degree <math>n</math> is equal to <math>2</math>, thus the whole complexity of algorithm in such case may be estimated as <math>O(\log p)</math> per iteration<ref name=":2" />.

== References ==