doi: 10.3934/amc.2022007
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm

Applied Statistics Unit, Indian Statistical Institute, 203, B.T. Road, Kolkata, India 700108

*Corresponding author: Palash Sarkar

Received  July 2021 Revised  November 2021 Early access February 2022

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

Citation: Palash Sarkar. Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm. Advances in Mathematics of Communications, doi: 10.3934/amc.2022007
References:
[1]

L. M. Adleman, K. L. Manders and G. L. Miller, On taking roots in finite fields, in 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), IEEE Computer Society, (1977), 175–178.

[2]

A. O. L. Atkin, Probabilistic primality testing, in INRIA Res. Rep., (1992), 159–163.

[3] E. Bach and J. Shallit, Algorithmic Number Theory Volume 1, Efficient Algorithms, Foundations of Computing Series. MIT Press, Cambridge, MA, 1996. 
[4]

D. J. Bernstein, Faster square roots in annoying finite fields, https://cr.yp.to/papers.html#sqroot, 2001.

[5]

D. J. Bernstein., Pippenger's exponentiation algorithm., https://cr.yp.to/papers.html#pippenger, 2002.

[6]

Z. CaoQ. Sha and X. Fan, Adleman-Manders-Miller root extraction method revisited, Lecture Notes in Computer Science, 7537 (2011), 77-85. 

[7]

M. Cipolla, Un metodo per la risolutione della congruenza di secondo grado, Rendiconto dell'Accademia Scienze Fisiche e Matematiche, Napoli, Series 3, (1903), 154–163.

[8]

H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag Berlin Heidelberg, 1993. doi: 10.1007/978-3-662-02945-9.

[9]

F. KongZ. CaiJ. Yu and D. Li, Improved generalized Atkin algorithm for computing square roots in finite fields, Inform. Process. Lett., 98 (2006), 1-5.  doi: 10.1016/j.ipl.2005.11.015.

[10]

D. H. Lehmer, Computer technology applied to the theory of numbers, MAA Studies in Number Theory, Prentice-Hall, Englewood Cliffs, N. J., 6 (1969), 117–151.

[11]

S. Lindhurst, An analysis of Shanks algorithm for computing square roots in finite fields, CRM Proceedings and Lecture Notes, 19 (1999), 231-242. 

[12]

S. Müller, On the computation of square roots in finite fields, Des. Codes Cryptogr., 31 (2004), 301-312.  doi: 10.1023/B:DESI.0000015890.44831.e2.

[13]

A. S. Rotaru and S. Iftene, A complete generalization of Atkin's square root algorithm, Fund. Inform., 125 (2013), 71-94.  doi: 10.3233/FI-2013-853.

[14]

D. Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics, Congressus Numerantium, Utilitas Mathematica, 7 (1973), 51–70.

[15]

A. Tonelli, Bemerkung über die auflösung quadratischer congruenzen, Göttinger Nachrichten, (1891), 344–346.

show all references

References:
[1]

L. M. Adleman, K. L. Manders and G. L. Miller, On taking roots in finite fields, in 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), IEEE Computer Society, (1977), 175–178.

[2]

A. O. L. Atkin, Probabilistic primality testing, in INRIA Res. Rep., (1992), 159–163.

[3] E. Bach and J. Shallit, Algorithmic Number Theory Volume 1, Efficient Algorithms, Foundations of Computing Series. MIT Press, Cambridge, MA, 1996. 
[4]

D. J. Bernstein, Faster square roots in annoying finite fields, https://cr.yp.to/papers.html#sqroot, 2001.

[5]

D. J. Bernstein., Pippenger's exponentiation algorithm., https://cr.yp.to/papers.html#pippenger, 2002.

[6]

Z. CaoQ. Sha and X. Fan, Adleman-Manders-Miller root extraction method revisited, Lecture Notes in Computer Science, 7537 (2011), 77-85. 

[7]

M. Cipolla, Un metodo per la risolutione della congruenza di secondo grado, Rendiconto dell'Accademia Scienze Fisiche e Matematiche, Napoli, Series 3, (1903), 154–163.

[8]

H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag Berlin Heidelberg, 1993. doi: 10.1007/978-3-662-02945-9.

[9]

F. KongZ. CaiJ. Yu and D. Li, Improved generalized Atkin algorithm for computing square roots in finite fields, Inform. Process. Lett., 98 (2006), 1-5.  doi: 10.1016/j.ipl.2005.11.015.

[10]

D. H. Lehmer, Computer technology applied to the theory of numbers, MAA Studies in Number Theory, Prentice-Hall, Englewood Cliffs, N. J., 6 (1969), 117–151.

[11]

S. Lindhurst, An analysis of Shanks algorithm for computing square roots in finite fields, CRM Proceedings and Lecture Notes, 19 (1999), 231-242. 

[12]

S. Müller, On the computation of square roots in finite fields, Des. Codes Cryptogr., 31 (2004), 301-312.  doi: 10.1023/B:DESI.0000015890.44831.e2.

[13]

A. S. Rotaru and S. Iftene, A complete generalization of Atkin's square root algorithm, Fund. Inform., 125 (2013), 71-94.  doi: 10.3233/FI-2013-853.

[14]

D. Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics, Congressus Numerantium, Utilitas Mathematica, 7 (1973), 51–70.

[15]

A. Tonelli, Bemerkung über die auflösung quadratischer congruenzen, Göttinger Nachrichten, (1891), 344–346.

Table 1.  Comparison of the average case number of operations required by the new algorithm and the TS algorithm
$ n $ #TS new algorithm
$ k $ ops #tot
16 91 3 26.0[S]+26.0[M] 52.0
32 311 5 66.5[S]+68.0[M] 134.5
48 659 6 121.5[S]+114.0[M] 235.5
64 1135 7 181.0[S]+170.0[M] 351.0
80 1739 8 246.5[S]+231.5[M] 478.0
96 2471 9 313.5[S]+300.0[M] 613.5
$ n $ #TS new algorithm
$ k $ ops #tot
16 91 3 26.0[S]+26.0[M] 52.0
32 311 5 66.5[S]+68.0[M] 134.5
48 659 6 121.5[S]+114.0[M] 235.5
64 1135 7 181.0[S]+170.0[M] 351.0
80 1739 8 246.5[S]+231.5[M] 478.0
96 2471 9 313.5[S]+300.0[M] 613.5
Table 2.  Comparison of Bernstein's table look-up method with the new table look-up method
$ w=2 $ $ w=4 $
$ n=96 $ (94[S]+1178[M],1272,49) (92[S]+302[M],394,25)
(6,182[S]+338[M],520,49) (4,170[S]+122[M],292,25)
$ n=128 $ (126[S]+2082[M],2208,65) (124[S]+530[M],654,33)
(9,239[S]+514[M],753,65) (4,228[S]+194[M],422,33)
$ n=256 $ (254[S]+8252[M],8512,129) (252[S]+2082[M],2334,65)
(14,519[S]+1484[M],2003,129) (8,484[S]+514[M],998,65)
$ n=512 $ (510[S]+32898[M],33408,257) (508[S]+8258[M],8766,129)
(17,991[S]+4098[M],5089,257) (8,972[S]+1538[M],2501,129)
$ n=1024 $ (1022[S]+131330[M],132352,513) (1020[S]+32898[M],33918,257)
(19,2087[S]+11801[M],13888,513) (16,1996[S]+4098[M],6094,257)
$ w=6 $ $ w=8 $
$ n=96 $ (90[S]+138[M],228,17) (88[S]+80[M],168,13)
(2,146[S]+82[M],228,17) (1,100[S]+80[M],180,13)
$ n=128 $ (122[S]+255[M],377,42) (120[S]+138[M],258,17)
(3,235[S]+115[M],350,29) (1,136[S]+138[M],274,17)
$ n=256 $ (250[S]+948[M],1198,84) (248[S]+530[M],778,33)
(4,469[S]+332[M],801,53) (4,448[S]+194[M],642,33)
$ n=512 $ (506[S]+3743[M],4249,170) (504[S]+2082[M],2586,65)
(5,1057[S]+955[M],2012,103) (8,960[S]+514[M],1474,65)
$ n=1024 $ (1018[S]+14708[M],15726,340) (1016[S]+8258[M],9274,129)
(16,2241[S]+2378[M],4619,188) (8,1928[S]+1538[M],3466,129)
$ w=2 $ $ w=4 $
$ n=96 $ (94[S]+1178[M],1272,49) (92[S]+302[M],394,25)
(6,182[S]+338[M],520,49) (4,170[S]+122[M],292,25)
$ n=128 $ (126[S]+2082[M],2208,65) (124[S]+530[M],654,33)
(9,239[S]+514[M],753,65) (4,228[S]+194[M],422,33)
$ n=256 $ (254[S]+8252[M],8512,129) (252[S]+2082[M],2334,65)
(14,519[S]+1484[M],2003,129) (8,484[S]+514[M],998,65)
$ n=512 $ (510[S]+32898[M],33408,257) (508[S]+8258[M],8766,129)
(17,991[S]+4098[M],5089,257) (8,972[S]+1538[M],2501,129)
$ n=1024 $ (1022[S]+131330[M],132352,513) (1020[S]+32898[M],33918,257)
(19,2087[S]+11801[M],13888,513) (16,1996[S]+4098[M],6094,257)
$ w=6 $ $ w=8 $
$ n=96 $ (90[S]+138[M],228,17) (88[S]+80[M],168,13)
(2,146[S]+82[M],228,17) (1,100[S]+80[M],180,13)
$ n=128 $ (122[S]+255[M],377,42) (120[S]+138[M],258,17)
(3,235[S]+115[M],350,29) (1,136[S]+138[M],274,17)
$ n=256 $ (250[S]+948[M],1198,84) (248[S]+530[M],778,33)
(4,469[S]+332[M],801,53) (4,448[S]+194[M],642,33)
$ n=512 $ (506[S]+3743[M],4249,170) (504[S]+2082[M],2586,65)
(5,1057[S]+955[M],2012,103) (8,960[S]+514[M],1474,65)
$ n=1024 $ (1018[S]+14708[M],15726,340) (1016[S]+8258[M],9274,129)
(16,2241[S]+2378[M],4619,188) (8,1928[S]+1538[M],3466,129)
[1]

Vincenzo Ambrosio, Giovanni Molica Bisci, Dušan Repovš. Nonlinear equations involving the square root of the Laplacian. Discrete and Continuous Dynamical Systems - S, 2019, 12 (2) : 151-170. doi: 10.3934/dcdss.2019011

[2]

Partha Sharathi Dutta, Soumitro Banerjee. Period increment cascades in a discontinuous map with square-root singularity. Discrete and Continuous Dynamical Systems - B, 2010, 14 (3) : 961-976. doi: 10.3934/dcdsb.2010.14.961

[3]

Theresa Lange, Wilhelm Stannat. Mean field limit of Ensemble Square Root filters - discrete and continuous time. Foundations of Data Science, 2021, 3 (3) : 563-588. doi: 10.3934/fods.2021003

[4]

Vito Mandorino. Connecting orbits for families of Tonelli Hamiltonians. Journal of Modern Dynamics, 2012, 6 (4) : 499-538. doi: 10.3934/jmd.2012.6.499

[5]

Jinmyong An, Roesong Jang, Jinmyong Kim. Global existence and blow-up for the focusing inhomogeneous nonlinear Schrödinger equation with inverse-square potential. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022111

[6]

Neal Koblitz, Alfred Menezes. Another look at security definitions. Advances in Mathematics of Communications, 2013, 7 (1) : 1-38. doi: 10.3934/amc.2013.7.1

[7]

Neal Koblitz, Alfred Menezes. Another look at generic groups. Advances in Mathematics of Communications, 2007, 1 (1) : 13-28. doi: 10.3934/amc.2007.1.13

[8]

Wenxing Zhu, Yanpo Liu, Geng Lin. Speeding up a memetic algorithm for the max-bisection problem. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 151-168. doi: 10.3934/naco.2015.5.151

[9]

Alessandro Ferriero. A direct proof of the Tonelli's partial regularity result. Discrete and Continuous Dynamical Systems, 2012, 32 (6) : 2089-2099. doi: 10.3934/dcds.2012.32.2089

[10]

Santanu Sarkar, Subhamoy Maitra. Some applications of lattice based root finding techniques. Advances in Mathematics of Communications, 2010, 4 (4) : 519-531. doi: 10.3934/amc.2010.4.519

[11]

Subhabrata Samajder, Palash Sarkar. Another look at success probability of linear cryptanalysis. Advances in Mathematics of Communications, 2019, 13 (4) : 645-688. doi: 10.3934/amc.2019040

[12]

Markus Kunze. A second look at the Kurth solution in galactic dynamics. Kinetic and Related Models, 2022, 15 (4) : 651-662. doi: 10.3934/krm.2021028

[13]

Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409

[14]

Yan Liu, Minjia Shi, Hai Q. Dinh, Songsak Sriboonchitta. Repeated-root constacyclic codes of length $ 3\ell^mp^s $. Advances in Mathematics of Communications, 2020, 14 (2) : 359-378. doi: 10.3934/amc.2020025

[15]

Tingting Wu, Shixin Zhu, Li Liu, Lanqiang Li. Repeated-root constacyclic codes of length 6lmpn. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021044

[16]

Neal Koblitz, Alfred Menezes. Critical perspectives on provable security: Fifteen years of "another look" papers. Advances in Mathematics of Communications, 2019, 13 (4) : 517-558. doi: 10.3934/amc.2019034

[17]

Dong Li, Tong Li. Shock formation in a traffic flow model with Arrhenius look-ahead dynamics. Networks and Heterogeneous Media, 2011, 6 (4) : 681-694. doi: 10.3934/nhm.2011.6.681

[18]

Jonathan D. Touboul. The hipster effect: When anti-conformists all look the same. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4379-4415. doi: 10.3934/dcdsb.2019124

[19]

David Hales, Stefano Arteconi. Motifs in evolving cooperative networks look like protein structure networks. Networks and Heterogeneous Media, 2008, 3 (2) : 239-249. doi: 10.3934/nhm.2008.3.239

[20]

A. Marigo. Robustness of square networks. Networks and Heterogeneous Media, 2009, 4 (3) : 537-575. doi: 10.3934/nhm.2009.4.537

2021 Impact Factor: 1.015

Article outline

Figures and Tables

[Back to Top]