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

1,756

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

Share:
1,756
spin
Author by

spin

Updated on August 01, 2022

Comments

  • spin
    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
      Jyrki Lahtonen over 10 years
      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 :-(
  • spin
    spin over 10 years
    Thanks for the answer, do you have a proof or a reference to the upper bound $\sqrt{p} + 1$?
  • Ivan Loh
    Ivan Loh over 10 years