On taking square roots without quadratic nonresidues over finite fields

Sze, Tsz-Wo

doi:10.1090/S0025-5718-2011-02419-1

On taking square roots without quadratic nonresidues over finite fields
HTML articles powered by AMS MathViewer

by Tsz-Wo Sze; \\ with an Appendix by Lawrence C. Washington PDF

Math. Comp. 80 (2011), 1797-1811 Request permission

Abstract:

We present a novel idea to compute square roots over finite fields, without being given any quadratic nonresidue, and without assuming any unproven hypothesis. The algorithm is deterministic and the proof is elementary. In some cases, the square root algorithm runs in $\tilde {O}(\log ^2 q)$ bit operations over finite fields with $q$ elements. As an application, we construct a deterministic primality-proving algorithm, which runs in $\tilde {O}(\log ^3 N)$ for some integers $N$.

References

Leonard Adleman, Kenneth Manders, and Gary Miller, On taking roots in finite fields, 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977) IEEE Comput. Sci., Long Beach, Calif., 1977, pp. 175–178. MR 0502224
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 45159, DOI 10.2307/1969420
Eric Bach, A note on square roots in finite fields, IEEE Trans. Inform. Theory 36 (1990), no. 6, 1494–1498. MR 1080838, DOI 10.1109/18.59955
Eric Bach and Klaus Huber, Note on taking square-roots modulo $N$, IEEE Trans. Inform. Theory 45 (1999), no. 2, 807–809. MR 1677049, DOI 10.1109/18.749034
Paulo S. L. M. Barreto and José Felipe Voloch, Efficient computation of roots in finite fields, Des. Codes Cryptogr. 39 (2006), no. 2, 275–280. MR 2209942, DOI 10.1007/s10623-005-4017-5
E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X
Daniel J. Bernstein, Faster square roots in annoying finite fields, 2001, preprint (http://cr.yp.to/papers/sqroot.pdf).
Johannes Buchmann and Victor Shoup, Constructing nonresidues in finite fields and the extended Riemann hypothesis, Math. Comp. 65 (1996), no. 215, 1311–1326. MR 1348040, DOI 10.1090/S0025-5718-96-00751-X
Michele Cipolla, Un metodo per la risoluzione della congruenza di secondo grado, Napoli Rend. 9 (1903), 154–163.
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
Martin Fürer, Faster integer multiplication, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 57–66. MR 2402428, DOI 10.1145/1250790.1250800
Hendrik W. Lenstra Jr. and Carl Pomerance, Primality testing with Gaussian periods, 2009, preprint (http://math.dartmouth.edu/~carlp/aks102309.pdf).
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. America, Buffalo, N.Y.; distributed by Prentice-Hall, Englewood Cliffs, N.J., 1969, pp. 117–151. MR 0246815
Gary L. Miller, Riemann’s hypothesis and tests for primality, Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N.M., 1975), Assoc. Comput. Mach., New York, 1975, pp. 234–239. MR 0480296
Siguna Müller, On probable prime testing and the computation of square roots mod $n$, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 423–437. MR 1850623, DOI 10.1007/10722028_{2}7
Siguna Müller, On the computation of square roots in finite fields, Des. Codes Cryptogr. 31 (2004), no. 3, 301–312. MR 2047886, DOI 10.1023/B:DESI.0000015890.44831.e2
Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI 10.1137/0209024
René C. Peralta, A simple and fast probabilistic algorithm for computing square roots modulo a prime number, IEEE Trans. Inform. Theory 32 (1986), no. 6, 846–847. MR 868931, DOI 10.1109/TIT.1986.1057236
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. MR 0371855
Andrew V. Sutherland, Structure computation and discrete logarithms in finite abelian $p$-groups, 2009, preprint (http://arxiv.org/abs/0809.3413).
Tsz-Wo Sze, On solving univariate polynomial equations over finite fields and some related problems, Ph.D. thesis, University of Maryland, 2007.
—, Deterministic primality proving on Proth numbers, 2010, preprint (http://arxiv.org/abs/0812.2596).
Alberto Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen, Nachrichten der Akademie der Wissenschaften in Göttingen (1891), 344–346.
Stephen M. Turner, Square roots mod $p$, Amer. Math. Monthly 101 (1994), no. 5, 443–449. MR 1272944, DOI 10.2307/2974905
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
Lawrence C. Washington, Elliptic curves, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008. Number theory and cryptography. MR 2404461, DOI 10.1201/9781420071474
Hugh C. Williams, Édouard Lucas and primality testing, Canadian Mathematical Society Series of Monographs and Advanced Texts, vol. 22, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR 1632793