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 number <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x \in {\bf Z}/P{\bf Z}</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P = 2^{S}Q + 1(Q</tex> odd, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s &gt; 0)</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</tex> . However, the algorithm presented here is considerably faster for values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</tex> greater than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</tex> .