Berlekamp–Rabin algorithm: Difference between revisions

Revision as of 22:37, 27 July 2019

Latest revision as of 20:25, 19 June 2025

(50 intermediate revisions by 30 users not shown)

Line 1:

{{short description|Method in number theory}}

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">{{Статья|author=E. R. Berlekamp|year=1970|doi=10.1090/S0025-5718-1970-0276200-X|issn=00255718|выпуск=111|язык=en|страницы=713–735|издание=Mathematics of Computation|заглавие=Factoring polynomials over large finite fields|ссылка=https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/|том=24}}</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">{{Статья|автор=M. Rabin|год=1980|doi=10.1137/0209024|issn=00975397|выпуск=2|страницы=273–280|издание=SIAM Journal on Computing|заглавие=Probabilistic Algorithms in Finite Fields|ссылка=https://epubs.siam.org/doi/10.1137/0209024|том=9}}</ref>. The method was also independently discovered before Berlekamp by some other researchers<ref>{{Книга|автор=Donald E Knuth|год=1998|isbn=9780201896848|заглавие=The art of computer programming. Vol. 2 Vol. 2|ссылка=https://www.worldcat.org/title/art-of-computer-programming-vol-2/oclc/900627019&referer=brief_results}}</ref>.

[[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'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 Z_pF_p</math> with <math>p</math> elements. The method was discovered by [[Elwyn Berlekamp|Berlekamp]] in 1970<ref name=":0">{{Статья|author=E.cite R.journal Berlekamp|yearurl=1970|doi=10 https://www.1090ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ |issntitle=00255718 Factoring polynomials over large finite fields |выпускjournal=111 Mathematics of Computation |языкyear=en 1970 |страницыvolume=713–735 24 |изданиеissue=Mathematics of111 Computation|заглавиеpages =Factoring polynomials713–735 over|issn large= finite0025-5718 fields|ссылкаdoi =https://www 10.ams.org/mcom/1970-24-1111090/S0025-5718-1970-0276200-X/ |томlanguage=24 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 fieldfields. The algorithm was later modified by [[Michael O. Rabin|Rabin]] for arbitrary finite fieldfields in 1979.<ref name=":1">{{Статьяcite journal |авторauthor = M. Rabin |годtitle=1980 Probabilistic Algorithms in Finite Fields |doi=10.1137/0209024|issn=00975397|выпуск=2|страницы=273–280|изданиеjournal= SIAM Journal on Computing |заглавиеyear=Probabilistic Algorithms1980 in|volume= Finite9 Fields|ссылкаissue=https://epubs.siam.org/ 2 |pages = 273–280 |issn = 0097-5397 |doi/ = 10.1137/0209024 |томciteseerx=9 10.1.1.17.5653 }}</ref>. The method was also independently discovered before Berlekamp by some other researchers.<ref>{{Книгаcite book|автор author = Donald E Knuth |год author-link =1998 Donald E Knuth |isbn=9780201896848|заглавие title = The art of computer programming. Vol. 2 Vol. 2 |ссылкаdate =https://www.worldcat.org/title/art 1998 | publisher = Addison-of-computer-programmingWesley | isbn = 978-vol-2/0201896848| oclc/900627019&referer =brief_results 900627019 }}</ref>.

== History ==

The method was proposed by [[Elwyn Berlekamp]] in his 1970 work<ref name=":0" /> on polynomial factorization over finite fields. OriginalHis 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=2011|doi=10.1090/s0025-5718-2011-02419-1|issn=00255718|выпуск=275|страницы=1797–1811|издание=Mathematics of Computation|заглавие=On taking square roots without quadratic nonresidues over finite fields |ссылкаjournal=http://dx. Mathematics of Computation|year= 2011 |volume= 80 |issue= 275 |pages = 1797–1811 |issn = 0025-5718 |doi.org/ = 10.1090/s0025-5718-2011-02419-1 |томarxiv =800812.2591 |s2cid= 10249895 }}</ref> for finding square roots in <math>\mathbb Z_pF_p</math>.<ref>{{Статьяcite journal |авторauthor = R. Peralta|год=1986|doi=10.1109/TIT.1986.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.) |ссылкаjournal=https: IEEE Transactions on Information Theory |date=November 1986 |volume= 32 |issue= 6 |pages = 846–847 |issn = 0018-9448 |doi = 10.1109//ieeexploreTIT.ieee1986.org/document/1057236|том=32 }}</ref>. In 2000 Peralta's method was generalized for [[Cubic equation|cubic equations]].<ref>{{Статьяcite journal |авторauthor = C Padró, G Sáez |годtitle=2002 Taking cube roots in Zm |doijournal=10.1016/s0893-9659(02)00031-9 Applied Mathematics Letters |issndate=08939659August 2002 |выпускvolume=6 15 |страницыissue=703–708 6 |изданиеpages =Applied Mathematics703–708 Letters|заглавиеissn =Taking cube0893-9659 roots|doi in= Zm|ссылка=http://dx.doi.org/10.1016/s0893-9659(02)00031-9 |томdoi-access=15 }}</ref>.

== Statement of problem==

Let <math>p</math> be thean odd prime number. Consider the polynomial <math display="inline">f(x) = a_0 + a_1 x + \dotscdots + a_n x^n</math> over the field <math>\mathbb Z_pF_p\simeq \mathbb Z/p\mathbb Z</math> of remainders modulo <math>p</math>. OneThe havealgorithm toshould find all <math>\lambda_1,lambda</math> \dots,in <math>\lambda_kmathbb F_p</math> such that <math display="inline">f(\lambda_ilambda)\equiv= 0 \pmod p</math> for every possiblein <math>i\mathbb F_p</math>.<ref name=":1" /><ref name=":2">{{Книгаcite book|автор author = Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone |год url =1993 https://www.springer.com/gp/book/9780792392828 |isbn title =9780792392828 Applications of Finite Fields |издательствоdate = 1993 |publisher= Springer US |серия series = The Springer International Series in Engineering and Computer Science |заглавие=Applications ofisbn Finite= Fields|ссылка=https://www.springer.com/gp/book/9780792392828}}</ref>.

== Algorithm ==

=== Randomization ===

Let <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\dotscdots(x-\lambda_n)</math>. Finding all roots of suchthis polynomial is equivalent to finding its factorization into linear factors. To find such factorization it's 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 random element of <math>\mathbb Z_pF_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_pF_p</math> elements ===

Due to [[Euler's criterion]], for every [[monomial]] <math>(x-\lambda)</math> exactly one of following properties holds:<ref name=":0" />:

# MonomialThe monomial is equal to <math>x</math> if <math>\lambda = 0</math>,

# MonomialThe monomial divides <math display="inline">g_0(x)=(x^{(p-1)/2}-1)</math> if <math>\lambda</math> is [[quadratic residue]] modulo <math>p</math>,

# MonomialThe monomial divides <math display="inline">g_1(x)=(x^{(p-1)/2}+1)</math> if <math>\lambda</math> is quadratic non-residual modulo <math>p</math>.

Thus if <math>f_z(x)</math> is not divisible by <math>x</math>, which may be checked separately, then <math>f_z(x)</math> is equal to the product of [[Polynomial greatest common divisor|greatest common divisors]] <math>\gcd(f_z(x);g_0(x))</math> and <math>\gcd(f_z(x);g_1(x))</math>.<ref name=":2" />.

=== Berlekamp's method ===

PropertyThe writtenproperty above leads to the following algorithm:<ref name=":0" />:

# 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 consequently 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 abovebelow provide a non-trivial factorization of <math>f_z(x)</math>,

# Otherwise all roots of <math>f_z(x)</math> are either residues or non-residues simultaneously and one has to choose another <math>z</math>.

If <math>f(x)</math> is divisible by some non-linear [[Primitive polynomial (field theory)|primitive polynomial]] <math>g(x)</math> over <math>\mathbb Z_pF_p</math> then when calculating <math>\gcd</math> with <math>g_0(x)</math> and <math>g_1(x)</math> one will obtain a non-trivial factorization of <math>f_z(x)/g_z(x)</math>, thus algorithm allows to find all roots of arbitrary polynomials over <math>\mathbb Z_pF_p</math>.

=== Modular square root ===

Consider equation <math display="inline">x^2 \equiv a \pmod{p}</math> having elements <math>\beta</math> and <math>-\beta</math> as its roots. Solution of this equation is equivalent to factorization of polynomial <math display="inline">f(x) = x^2-a=(x-\beta)(x+\beta)</math> over <math>\mathbb Z_pF_p</math>. In this particular case problem is a bit simpler because it is sufficient to calculate only <math>\gcd(f_z(x); g_0(x))</math>. For this polynomial exactly one of the following properties will hold:

# GCD is equal to <math>1</math> which means that <math>z+\beta</math> and <math>z-\beta</math> are both quadratic non-residues,

Line 39 ⟶ 41:

# GCD is equal to <math>(x-t)</math>which means that exactly one of these numbers is quadratic residue.

In the third case GCD is equal to either <math>(x-z-\beta)</math> or <math>(x-z+\beta)</math>. It allows to write the solution as <math display="inline">\beta = (t - z) \pmod{p}</math>.<ref name=":0" />.

=== Example ===

Line 48 ⟶ 50:

# Let <math>z=2</math>. Then <math>f_z(x) = (x-2)^2 - 5 = x^2 - 4x - 1</math>, thus <math display="inline">\gcd( x^2 - 4x - 1 ; x^5 - 1)\equiv x - 9 \pmod{11}</math>. From this follows <math display="inline">x - 9 = x - 2 - \beta</math>, so <math>\beta \equiv 7 \pmod{11}</math> and <math display="inline">-\beta \equiv -7 \equiv 4 \pmod{11}</math>.

ManualA manual check shows that, indeed, <math display="inline">7^2 \equiv 49 \equiv 5\pmod{11}</math> and <math display="inline">4^2\equiv 16 \equiv 5\pmod{11}</math>.

== Correctness proof ==

AlgorithmThe 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 |год=1998|isbn=9780471315186|страниц=464|издательство=John Wileyurl & Sons|заглавие=Combinatorial Theory|ссылка=https://books.google.rucom/books?hl=en&lr=&id=__JCiiCfu2EC&oi=fnd&pg=PA1&dqq=Combinatorial+Theory+hall&otspg=WeNDZ7uCSM&sigPA1 | title =a6JwSPPen2C2EysEnkSTXpUNaxM&redir_esc Combinatorial Theory |date =y#v 1998 |publisher=onepage John Wiley &q Sons | isbn =Combinatorial%20Theory%20hall&f=false 9780471315186}}</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 differentdistinct values amongin <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 ==

AssumeLet thata polynomial's have degree is <math>n</math>. Here'sWe estimationderive ofthe algorithm's steps complexity as follows:

# Due to the [[binomial theorem]] <math display="inline">(x-z)^k = \sum\limits_{i=0}^k \binom{k}{i} (-z)^{k-i}x^i</math>, thuswe may transition from <math>f(x)</math> to <math>f(x-z)</math> may be done in <math>O(n^2)</math>, time.

# Polynomial multiplication and taking remainder of one polynomial modulo another one may be done in <math display="inline">O(n^2)</math>, thus calculation of <math display="inline">x^{2^k} \bmod f_z(x)</math> is done in <math display="inline">O(n^2 \log p)</math>,.

# Binary exponentiation works in <math>O(n^2 \log p)</math> as well,.

# Taking the <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 the [[fast Fourier transform]] and Half-GCD algorithm,<ref>{{Книгаcite book |автор author = Aho, Alfred V. |год url =1974|isbn=0201000296|издательство=Addison-Wesley Pubhttps://archive.org/details/designanalysisof00ahoarich Co|заглавие title = The design and analysis of computer algorithms |ссылка date =http://worldcat 1974 | publisher = Addison-Wesley Pub.org/oclc/1147299 Co | isbn = 0201000296 | url-access = registration }}</ref> the algorithm's complexity may be improved to <math>O(n \log n \log pn)</math>. For the modular square root case, the degree is <math>n</math> is= equal to <math>2</math>, thus the whole complexity of algorithm in such case may beis estimatedbounded asby <math>O(\log p)</math> per iteration.<ref name=":2" />.

== References ==

{{reflist}}

{{примечания}}{{Number-theoretic algorithms}}<br />

{{примечания}}{{Number-theoretic algorithms}}<br />

[[Category:Algorithms]]

[[Category:Algebra]]