Berlekamp–Rabin algorithm: Difference between revisions

Revision as of 01:31, 10 December 2020

Revision as of 13:50, 2 February 2021

Line 3:

== 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 = 00255718 |doi = 10.1090/s0025-5718-2011-02419-1 |arxiv =0812.2591 |s2cid= 10249895 }}</ref> for finding square roots in <math>\mathbb Z_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 = 00189448 |doi = 10.1109/TIT.1986.1057236 }}</ref> In 2000 Peralta's method was generalized for 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 = 08939659 |doi = 10.1016/s0893-9659(02)00031-9 }}</ref>

== Statement of problem==

Line 52:

== 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&pg=PA1&dqq=Combinatorial+Theory+hall#v=onepage&qpg=Combinatorial%20Theory%20hall&f=falsePA1 | 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 ==