Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm

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