Paper 2020/1407
Computing Square Roots Faster than the TonelliShanks/Bernstein Algorithm
Palash Sarkar
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 nonsquare $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 $(m1)/2$. This improves upon the TonelliShanks (TS) algorithm which requires $\mathfrak{T}+O(n^{2})$ operations. Bernstein had proposed a table lookup 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 lookup 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 square rootTonelliShanks algorithmtable lookup
 Contact author(s)
 palash @ isical ac in
 History
 20211129: last of 7 revisions
 20201115: received
 See all versions
 Short URL
 https://ia.cr/2020/1407
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1407, author = {Palash Sarkar}, title = {Computing Square Roots Faster than the TonelliShanks/Bernstein Algorithm}, howpublished = {Cryptology ePrint Archive, Paper 2020/1407}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1407}}, url = {https://eprint.iacr.org/2020/1407} }