# Determine the set of odd primes for which a quadratic residue modulo $p$, $p$ 'large'

though this one may seem a duplicate of - say - this: Determine all primes $p$ for which $5$ is a quadratic residue modulo $p$, well, I have a question. How would you manage the problem of determining the set of odd primes for which a quadratic residue modulo $p$, when $p$ is 'large'. For instance, suppose $p=29$. Then, one applies the quadratic reciprocity law obtaining: $$\left(\frac{29}{p}\right)=\left(\frac{p}{29}\right)\cdot\left(-1\right)^{\left(p-1\right)\left(29-1\right)/4}$$

So we need to study the following:

1. the sign of the Legendre symbol, so the values of $p$ modulo $29$
2. the parity of $\left(-1\right)^{\left(p-1\right)/2}$ modulo 2, or the parity of $p$ modulo $4$

Now, this suggests to consider values of $p$ modulo $29\cdot4=116$ and since $\varphi\left(116\right)=56$, this approach is surely exhaustive, though there must be a more clever, and faster way. Any suggestion?

Since the final answer will necessarily look like "$29$ is a quadratic residue modulo $p$ if and only if $p\mod 116$ is one of the following values ..." a more clever and faster way can hardly be imagined.