# Algorithm to find all quadratic residues modulo $n$

An element $a \in \mathbb{Z}_n$ is a quadratic residue in $\mathbb{Z}_n$ if it's congruent to some perfect square modulo $n$.

Is there an efficient algorithm to find all quadratic residues in $\mathbb{Z}_n$?
$n$ is composite and we know all it's factors if that helps.

Update:

We have one more restriction: $n$ = $p_1 p_2 \dots p_k$, where $p_i$ are distinct odd primes and $p_i \equiv 3 \pmod 4$. Can we get something in this case?

I use the following approach at the moment:
Iterate over $\left\lfloor\frac{n}{2}\right\rfloor + 1$ perfect squares starting from $0$ and store them as we go. The problem is that it becomes slow quickly as $n$ grows. Here's the code example:

#include <stdio.h>

int main() {
int n = 7 * 11;
int qr = 0;
int step = 1;

for (int i = 0;i <= n / 2;i++) {
printf("qr: %i\n", qr);

// perform some operation on qr here
// e.g. store it somewhere to access later

qr = (qr + step) % n;
step += 2;
}

return 0;
}

• You can maybe do better by factorizing $n$ into prime powers and reducing the problem to listing residues modulo a prime power, as in en.wikipedia.org/wiki/Quadratic_residue#Prime_power_modulus – Kirill Mar 21 '17 at 0:41
• Given that the output is $O(n)$ numbers, there is not much space to improve here... – Federico Poloni Mar 21 '17 at 19:21
• @Kirill This is a great idea! The only thing I don't understand is how to efficiently list all QR modulo $n$ once we find the lists of QR modulo every prime power dividing $n$. – nrg Mar 25 '17 at 13:08
• @FedericoPoloni That was my first thought too, but it seems that only really works for some numbers, like primes: oeis.org/A000224 Up to $10^4$, the smallest you can get is 9360, with just 336 squares (3% of $n$). With $k$ distinct prime factors, there will be something like $2^{-k}n$ residues, so depending on $n$ it can be meaningful (not in general, though). – Kirill Mar 25 '17 at 15:54
• @nrg The Wikipedia article tells you how to do just that: list the residues modulo the individual prime powers, then take products of combinations of them. – Kirill Mar 25 '17 at 16:00

$$\frac{(p_1-1)}{2} \frac{(p_2-1)}{2} \cdots \frac{(p_k-1)}{2}$$
congruence system of the form $x=q(\mod\ p_i)$ where $q$ is $1^2, 2^2, 3^2, \cdots, \left(\frac{(p_i-1)}{2}\right)^2$ using Chinese remainder theorem.
This will give you all the distinct $(p_1-1)/2\ (p_2-1)/2 \cdots (p_k-1)/2$ square solutions.