# Computing Square Roots Faster than the Tonelli-Shanks/Bernstein Algorithm, by Palash Sarkar

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\$.