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 :
