On Shanks' Algorithm for Modular Square Roots

Abstract

Let $p$ be a prime number, $p=2^{n}q+1$, where $q$ is odd. D. Shanks described an algorithm to compute square roots $(\mathrm{mod}p)$ which needs $O(\log q+n^2)$ modular multiplications. In this note we describe two modifications of this algorithm. The first needs only $O(\log q+n^{3/2})$ modular multiplications, while the second is a parallel algorithm which needs $n$ processors and takes $O(\log q+n)$ time.