Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On taking square roots without quadratic nonresidues over finite fields

Author: Tsz-Wo Sze; \\ with an Appendix by Lawrence C. Washington
Journal: Math. Comp. 80 (2011), 1797-1811
MSC (2010): Primary 12Y05; Secondary 11Y16, 11Y11
Published electronically: January 3, 2011
MathSciNet review: 2785480
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


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

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
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.