Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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


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$.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 12Y05, 11Y16, 11Y11
  • Retrieve articles in all journals with MSC (2010): 12Y05, 11Y16, 11Y11
Additional Information
  • Tsz-Wo Sze
  • Affiliation: Department of Computer Science, University of Maryland, College Park, Maryland 20742
  • Email:
  • 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:
  • MathSciNet review: 2785480