Let $p$ be a large odd prime, and $k$ the prime field ${\bf Z} / p {\bf Z}$. We give deterministic polynomial-time reductions between the problems of extracting a square root of an arbitrary square $a \in k$ and finding a single non-square $g \in k$ [NB testing whether $a \in k^\times$ is a square is polynomial time by Legendre’s criterion involving $a^{(p-1)/2}$.]
Recall that $k^\times$ is a cyclic group of order $p-1$; write $p-1 = 2^e m$ with $m$ odd; clearly $0 < e < \log_2 p$.
Given an oracle that compute a square root of $a$ for any $a \in (k^\times)^2$, we can obtain a “quadratic nonresidue” $g$ [should really be called a “nonquadratic residue”…], by applying the oracle $e-1$ times: if $e=1$ then set $g = -1$; if $e=2$ then $g$ can be either square root of $-1$; if $e=3$, a square root of a square root of $-1$; and so forth. So, finding $g$ reduces to $e-1$ square-root extractions.
Of course if $e = 1$ we can take $g = -1$;
also if $e = 2$ (so $p \equiv 5 \bmod 8$) then $g=2$ works without
ever having to invoke our square-root oracle. Likewise if $e=3$
(so $p \equiv 9 \bmod 16$) then $2$ is a square, but $2 \pm \sqrt 2$ is not,
and we can compute a square root of $2$ deterministically
as the product of square roots of $-1$ and $-2$ that we compute by
applying Schoof’s algorithm to CM (complex multiplication)
elliptic curves of
In the other direction, suppose $g \in k^\times$ is a non-square
and $a$ is a square. We shall find a nonnegative integer $n < 2^{e-1}$
such that $g^{2n} a$ is in the subgroup $\{z \in k^\times : z^m = 1\}$
of $k^\times$. The square roots of such $z$ are $\pm z^{(m+1)/2}$;
so $g^{2n} a$ will have square root $r = (g^{2n} a)^{(m+1)/2}$,
and then $g^{-n} r$ will be a square root
If $e=1$ and $a \in k^\times$ is square then $a^m = 1,$ so $n=0$ works. I If $e=2$, we take $n=0$ if $a^m = 1$, and $n=1$ if not. In general, start from $n=0$ and do the following for each $i = 1, 2, \ldots, e-1$:
If $(g^n a)^{2^{e-i}m} = 1$, do nothing.We claim that after the $i$-th step we have $(g^n a)^{2^{e-i}m} = +1$. We prove this by induction on $i$, starting from $i=0$ (that is, before starting the loop). At that point we claim $a^{(p-1)/2} = +1$, which is true by hypothesis ($a \in {k^\times}^2$). Then, assuming the result for $i-1$, we see that before the $i$-th step we already had either $((g^n a)^{2^{e-i}m})^2 = 1$, so $(g^n a)^{2^{e-i}m}$ is either $+1$ or $-1$. In the former case we did nothing; in the latter, we multiplied $g^n a$ by $g^{2^{i-1}}$, and thus multiplied $(g^n a)^{2^{e-i}m}$ by $$ g^{2^{i-1}m} = g^{(p-1)/2} = -1, $$ so indeed $(g^n a)^{2^{e-i}m} = +1$ after the $i$-th step. This completes the induction step and the proof. Thus when we reach $i=e$ we have $(g^n a)^m = 1$ as desired. Moreover $n$ is clearly a nonnegative integer that is at most $1 + 2 + 4 + \cdots + 2^{e-2} < 2^{e-1}.$ QED
Else $(g^n a)^{2^{e-i}m} = -1$, in which case change $n$ to $n+2^{i-1}$.