The first $4$ primes $p$ for which $15347$ has a square root mod $p$ are $2, 17, 23,$ and $29$

Question

I am reading about Quadratic Sieve article in wiki and I don't understand the sieve part.

The article says:

The first $4$ primes $p$ for which $15347$ has a square root mod $p$ are $2, 17, 23,$ and $29$

How $2,17,23,$ and $29$ been calculated? If you can, please explain me the idea and the exact calculation.

Answer 1

You could use quadratic reciprocity, as suggested in the comments, but those primes are so small that a brute-force approach is also reasonable. To find out whether a large $n$ has a square root modulo a small prime $p$, first compute $x = n \bmod p$, and then check whether $y^2 \equiv x \bmod p$ for some $y \in \{0,1,\ldots,(p-1)/2\}$.