0
$\begingroup$

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;
}
$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Kirill Mar 21 '17 at 0:41
  • 2
    $\begingroup$ Given that the output is $O(n)$ numbers, there is not much space to improve here... $\endgroup$ – Federico Poloni Mar 21 '17 at 19:21
  • $\begingroup$ @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$. $\endgroup$ – nrg Mar 25 '17 at 13:08
  • 1
    $\begingroup$ @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). $\endgroup$ – Kirill Mar 25 '17 at 15:54
  • 1
    $\begingroup$ @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. $\endgroup$ – Kirill Mar 25 '17 at 16:00
0
$\begingroup$

You need to solve

$$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.