If $p \equiv 1 \mod{4}$ is prime, how to find a quadratic nonresidue modulo $p$?
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}$
spin
Updated on August 01, 2022Comments
-
spin over 1 year
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$.
-
Jyrki Lahtonen over 10 yearsTwo is a quadratic non-residue, if $p\equiv 5\pmod8$. Doesn't work when $p\equiv 1\pmod8$, so only solves half of your problem :-(
-
-
spin over 10 yearsThanks for the answer, do you have a proof or a reference to the upper bound $\sqrt{p} + 1$?
-
Ivan Loh over 10 years
