z-logo
open-access-imgOpen Access
Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm
Author(s) -
Palash Sarkar
Publication year - 2024
Publication title -
advances in mathematics of communications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.601
H-Index - 26
eISSN - 1930-5346
pISSN - 1930-5338
DOI - 10.3934/amc.2022007
Subject(s) - mathematics , combinatorics , algebra over a field , discrete mathematics , arithmetic , pure mathematics
Let \begin{document}$ p $\end{document} be a prime such that \begin{document}$ p = 1+2^nm $\end{document} , where \begin{document}$ n\geq 1 $\end{document} and \begin{document}$ m $\end{document} is odd. Given a square \begin{document}$ u $\end{document} in \begin{document}$ \mathbb{Z}_p $\end{document} and a non-square \begin{document}$ z $\end{document} in \begin{document}$ \mathbb{Z}_p $\end{document} , we describe an algorithm to compute a square root of \begin{document}$ u $\end{document} which requires \begin{document}$ \mathfrak{T}+O(n^{3/2}) $\end{document} operations (i.e., squarings and multiplications), where \begin{document}$ \mathfrak{T} $\end{document} is the number of operations required to exponentiate an element of \begin{document}$ \mathbb{Z}_p $\end{document} to the power \begin{document}$ (m-1)/2 $\end{document} . This improves upon the Tonelli-Shanks (TS) algorithm which requires \begin{document}$ \mathfrak{T}+O(n^{2}) $\end{document} operations. Bernstein had proposed a table look-up based variant of the TS algorithm which requires \begin{document}$ \mathfrak{T}+O((n/w)^{2}) $\end{document} operations and \begin{document}$ O(2^wn/w) $\end{document} storage, where \begin{document}$ w $\end{document} is a parameter. A table look-up variant of the new algorithm requires \begin{document}$ \mathfrak{T}+O((n/w)^{3/2}) $\end{document} operations and the same storage. In concrete terms, the new algorithm is shown to require significantly fewer operations for particular values of \begin{document}$ n $\end{document} .

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here