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
Additional Information
- Tsz-Wo Sze
- Affiliation: Department of Computer Science, University of Maryland, College Park, Maryland 20742
- Email: szetszwo@cs.umd.edu
- Lawrence C. Washington
- Affiliation: Department of Mathematics, University of Maryland, College Park, Maryland 20742
- Received by editor(s): September 20, 2009
- Received by editor(s) in revised form: February 9, 2010
- Published electronically: January 3, 2011
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 80 (2011), 1797-1811
- MSC (2010): Primary 12Y05; Secondary 11Y16, 11Y11
- DOI: https://doi.org/10.1090/S0025-5718-2011-02419-1
- MathSciNet review: 2785480