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

**Category / Keywords: **public-key cryptography / square root, Tonelli-Shanks algorithm, table look-up

**Date: **received 12 Nov 2020, last revised 7 Feb 2021

**Contact author: **palash at isical ac in

**Available format(s): **PDF | BibTeX Citation

**Note: **Corrected some minor typos.

**Version: **20210208:053938 (All versions of this report)

**Short URL: **ia.cr/2020/1407

[ Cryptology ePrint archive ]