Paper 2020/1407

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

Palash Sarkar


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

Note: Minor revision.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
square rootTonelli-Shanks algorithmtable look-up
Contact author(s)
palash @ isical ac in
2021-11-29: last of 7 revisions
2020-11-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Palash Sarkar},
      title = {Computing Square Roots Faster than the Tonelli-Shanks/Bernstein Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1407},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.