Content deleted Content added
|
|
|
== 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 |editor= |format= |url= httphttps://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= |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 =0812.2591 |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=November 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= httphttps://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=August 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 of Problem==
|
