Finding a prime which is a square modulo all small primes

Question

I want to find a small prime $p$ satisfying

• $p\equiv 1 \pmod{8}$
• $\left(\frac{p}{q} \right) = 1$ for all primes $3 \leq q \leq N$

where $N$ is a moderately large number (say, around $15,000$). I want $p$ to be small, say at most the cube root of the modulus.

Is this computationally feasible? I am not too familiar with what is and isn't reasonable to do with modern computing, so this might be a very naive question.

Answer 1

You can address this problem with Coppersmith's method - check out this answer for detail.

Answer 2

Honorable mention goes to the number $15073$. This prime number is not a quadratic residue $\bmod p$ for a long list of small primes; its residues $3\bmod5$ and $6\bmod13$ are nonquadratic. But it is the smallest prime that is a quadratic residue modulo all the Heegner primes $2,3,7,11,19,43,67,163$ for which the imaginary quadratic field with $-p$ as radicand has unique factorization of the integers; and with respect to the prime $2$ also meeting the more stringent requirement of being a $2$-adics square (residue $1\bmod 8$). This property makes $(15073)$ the smallest natural-prime ideal that splits in all the class-1 imaginary quadratic fields.

Answer 3

These are pseudosquares. The first $73$ are tabulated at https://oeis.org/A002189 and many references to the literature are given.

Thanks to @Oscar Lanzi for pointing out that OP only wants prime pseudosquares. The links at the oeis site still give some useful information on best methods for finding pseudosquares, and estimates for how fast they grow.