# Finding a non-quadratic residue mod $p$

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?

• The legendre-symbol can be calculated efficiently and decides whether a given integer is a quadratic residue mod $p$ – Peter Jun 4 '18 at 8:51
• @Peter I know that quadratic reciprocity makes the computation of Legendre symbol very easy (maybe $O(\log n)$?), but I hope there's much simple way to do this. – Seewoo Lee Jun 4 '18 at 9:58
• If you are interested in the practical aspect, the fastest way is simply to choose randomly in $\{2,p-2\}$ and test whether it is non-quadratic residue. On average only two tries are required and since the test is fast you find it very easily. (Say via Euler's criterion.) For example this is what is commonly done for the Tonelli–Shanks algorithm does. One of the substeps requires finding a non-quadratic residue. – Yong Hao Ng Jun 5 '18 at 8:37

## 1 Answer

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.

• Is finding $q$ easy in general? If it is, then this will be a good way. – Seewoo Lee Jun 4 '18 at 9:59
• Basically I would use trial and error. You could also find a primitive root and you're good with that, but this is not straightforward, either. – Oscar Lanzi Jun 4 '18 at 10:49