DocumentCode
942197
Title
A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
Author
Peralta, Rene C.
Volume
32
Issue
6
fYear
1986
fDate
11/1/1986 12:00:00 AM
Firstpage
846
Lastpage
847
Abstract
A probabilistic polynomial-time algorithm for computing the square root of a number 
, where 
odd, 
is a prime number, is described. In contrast to the Adleman, Manders, and Miller algorithm, this algorithm gets faster as s grows. As with the Berlekamp-Rabin algorithm, the expected running time of the algorithm is independent of 
. However, the algorithm presented here is considerably faster for values of 
greater than 
.
, where odd, is a prime number, is described. In contrast to the Adleman, Manders, and Miller algorithm, this algorithm gets faster as s grows. As with the Berlekamp-Rabin algorithm, the expected running time of the algorithm is independent of . However, the algorithm presented here is considerably faster for values of greater than .Keywords
Residue arithmetic; Square-rooting; Computer science; Equations; Polynomials;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/TIT.1986.1057236
Filename
1057236
Link To Document