Welcome to the resource topic for 2020/1407
Title:
Computing Square Roots Faster than the Tonelli-Shanks/Bernstein Algorithm
Authors: 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 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.
ePrint: https://eprint.iacr.org/2020/1407
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .