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