Paper 2020/1407

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

Palash Sarkar

Abstract

Let $p$ be a prime such that $p=1+2^{n}m$, where $n\ge 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^{w}n/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 $$.

Note: Minor revision.