Paper 2020/1407

Computing Square Roots Faster than the Tonelli-Shanks/Bernstein Algorithm

Palash Sarkar

Abstract

We describe an algorithm to compute square roots modulo a prime $p=1+2^nm$, with $m$ odd and $n\geq 1$, 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 variation 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 practical terms, the new algorithm is shown to require significantly less number of operations for concrete values of $n$.

Note: Corrected some minor typos.