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$.

  • 1
    $\begingroup$ Two 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 :-( $\endgroup$ – Jyrki Lahtonen Mar 15 '13 at 10:05

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}$

  • $\begingroup$ Thanks for the answer, do you have a proof or a reference to the upper bound $\sqrt{p} + 1$? $\endgroup$ – spin Mar 15 '13 at 12:23
  • 2
    $\begingroup$ See number.subwiki.org/wiki/… $\endgroup$ – Ivan Loh Mar 15 '13 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.