How to find all the Quadratic residues modulo $p$

Question

I want to implement Sieve improvement for Fermat's factorization method.

For that I need your help answering: How to find all the Quadratic residues modulo $p$?

$$\{x ~\vert~ x^2 \equiv q \pmod{p}\}$$

Answer 1

Perhaps I have misunderstood the question. But the obvious method is:

For $0 \le n \le \lfloor p/2\rfloor$, $n^2$ (mod $p$) is a quadratic residue mod $p$.

This generates all quadratic residues exactly once.

Answer 2

One way is to find a primitive root mod $p$.

If $g$ is a primitive root mod $p$, write $q = g^n$ and $x=g^k$.

Then the solutions of $x^2 \equiv q \bmod{p}$ correspond to the solutions of $2k \equiv n \bmod (p-1)$. This linear equation is easy to solve.

For example, take $p=31$. Then $g=3$ is a primitive root.

Take $q=19$. Then $n=4$ and $2k \equiv 4 \bmod 30$ gives $k=2$ and $k=17$, which gives $x=9$ and $x=22$.

Take $q=17$. Then $n=7$. But $2k \equiv 7\bmod 30$ has no solution and so $x^2 \equiv 17 \bmod 31$ has no solution.

If $q$ is not given and you only want to know the squares mod $p$, then they are $g^{n}$ with $n$ even.