Paper 2020/1407 Original: eprint.iacr.org/2020/1407 ↗

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

Abstract

Let $p$ be a prime such that $p=1+2^nm$, where $n\geq 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$.