  Let $p$ be a prime number, $p=2^nq+1$, where $q$ is odd. D. Shanks described
an algorithm to compute square roots $\pmod{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.

Number Theory