elementary number theory - If $p equiv 1 mod{4}$ is prime, how to find a quadratic nonresidue modulo $p$?

If $p \equiv 3 \mod{4}$ is prime, then $-1$ is a quadratic non-residue modulo $p$. This is not the case when $p \equiv 1 \mod{4}$. How can we find a quadratic non-residue in this case?

At least one will exist since half of the elements in $\mathbb{Z}_p^*$ are quadratic residues and the other half are non-residues, so atleast one non-residue will exist. What I am looking for is an algorithm (other than brute force or a probabilistic algorithm) or a formula that would describe some quadratic residue modulo $p$.

Answer

If $p \equiv 5 \pmod{8}$, $2$ is a quadratic non-residue $\pmod{p}$. If $p \equiv 1 \pmod{8}$, the smallest quadratic non-residue has to be an odd prime $q$, and by quadratic reciprocity $\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)$, so you can just take prime $q$ and test whether $p$ is a quadratic residue $\pmod{q}$. Do this for $q=3, 5, 7 \ldots$.

Edit: An efficient way to compute $\left(\frac{q}{p}\right)$ would be to use the Jacobi symbol Note: This is much faster than using the Legendre symbol.

This algorithm ends quite quickly, since it is known that the smallest quadratic non-residue is $<\sqrt{p}+1$, and if the extended Riemann hypothesis is true, then the smallest quadratic non-residue is $<\frac{3(\ln{p})^2}{2}$