Finding a non-quadratic residue mod $p$

Question

Let $p$ be an arbitrary big prime. Is there any fast algorithm to find a non-quadratic residue mod $p$? If $p\equiv 3(\,\mathrm{mod}\, 4)$, then $-1\equiv p-1$ is always a non-quadratic residue. However, if $p\equiv 1(\,\mathrm{mod}\, 4)$, then we can't just choose $p-1$. For $p\equiv 5(\,\mathrm{mod}\, 8)$, it is also known that $2$ is a non-quadratic residue, but we have to deal with the case when $p\equiv 1(\,\mathrm{mod}\, 8)$. Is there any easier way to do this?

Answer 1

One method, which works for all odd primes $p$ (no need to check the residue modulo 4 or modulo 8) is to seek an odd prime $q$ for which $p$ itself is (congruent to) a nonquadratic residue modulo $p$. Then by quadratic reciprocity you choose $q$ or $-q$ such that the choice has residue $1 \bmod 4$, and this choice is a nonquadratic residue mod $p$.

Example: $p=23$. Then $p=23\equiv 2 \bmod 3$, and $2$ is a nonquadratic residue modulo $3$. Since $-3 \equiv 1 \bmod 4$ we infer that $-3$ will be a nonquadratic residue modulo $23$.

Addendum

How many trials should we expect before hitting on a nomquadratic residue? For $q=3$, half of all larger primes give a nomquadratic residue modulo $3$ (meaning $2 \bmod 3$ instead of $1 \bmod 3$). We get the same 50% probability for each additional prime $q$, so on average two trials is usually enough. But what if, metaphorically, the coin keeps coming up tails?

Define $f(q)$ as follows:

• $q$ and $f(q)$ are both odd primes with $f(q)>q$.

• For every odd prime $p$ less than $f(q)$, a nonquadratic residue is found using a smaller trial prime than $q$, but $p=f(q)$ requires testing up to the prescribed value of $q$.

For instance, all odd primes $3<p<19$ give a nonquadratic residue using $q=3$ or $q=5$, but $p=19$ requires $q=7$. Then $f(7)=19$. We find that

$f(3)=5$

$f(5)=7$

$f(7)=19$

$f(11)=79$

$f(13)=151$

Based on probability arguments, it is expected that $2^n<f(q)<2^q$ where $q$ is the $n$-th odd prime in ascending order. For instance $q=7$ implies $n=3$, and $f(7)=19$ lies between $2^3=8$ and $2^7=128$. This is a wide range for the value of $f(q)$, but if the proposed range is true it guarantees that the maximum number of trials required for a large prime $p$ will be $O((\log p)^{1+\epsilon})$ for arbitrarily small positive $\epsilon$. The maximum drops to $O(\log p)$ if a list of primes is known or (nowadays) efficiently generated.