A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)

Abstract

A probabilistic polynomial-time algorithm for computing the square root of a numberx \in {\bf Z}/P{\bf Z}, whereP = 2^{S}Q + 1(Qodd,s > 0)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 ofx. However, the algorithm presented here is considerably faster for values ofsgreater than2.