Let $p$ be a prime such that $p=1+2^nm$, where $ngeq 1$ and $m$ is odd. Given a square $u$ in $mathbb{Z}_p$ and a non-square $z$ in $mathbb{Z}_p$,
we describe an algorithm to compute a square root of $u$ which requires $mathfrak{T}+O(n^{3/2})$ operations (i.e., squarings and multiplications), where $mathfrak{T}$
is the number of operations required to exponentiate an element of $mathbb{Z}_p$ to the power $(m-1)/2$. This improves upon the Tonelli-Shanks (TS) algorithm which
requires $mathfrak{T}+O(n^{2})$ operations. Bernstein had proposed a table look-up based variant of the TS algorithm which requires $mathfrak{T}+O((n/w)^{2})$
operations and $O(2^wn/w)$ storage, where $w$ is a parameter. A table look-up variant of the new algorithm requires $mathfrak{T}+O((n/w)^{3/2})$ operations and the
same storage. In concrete terms, the new algorithm is shown to require significantly fewer operations for particular values of $n$.

By admin