Cryptology ePrint Archive: Report 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$.

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:

[ Cryptology ePrint archive ]