On Taking Square Roots without Quadratic Nonresidues over Finite Fields

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

arXiv comment14 pages

References in corpus (1)

• Deterministic Primality Proving on Proth Numbers

Cited by in corpus (2)

• On Taking r-th Roots without r-th Nonresidues over Finite Fields and Its Applications
• PPT: New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues. A Set of Three Companion Manuscripts