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?
 A: 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.
