# A Query regarding Quadratic Residuocity Problem

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: $$x^2\equiv q \pmod{n}.$$Otherwise, q is called a quadratic nonresidue modulo n.

Problem Definition: Given a constant c, is there a positive integer x < c such that $$x^2\equiv q \pmod{n}.$$

If n is composite, the problem is NP-Complete, even if given the prime factorization of n. But, if n is a prime the problem is solvable in polynomial time.

Query: In case n is composite, and given that it has lets say exactly 3 distinct prime factors, does the problem still remain NP-Complete? Any link to the references?

• Have you looked at the NP-hardness proof? – Yuval Filmus May 28 '15 at 5:23
• I did not have a look at the proof but know the from from G&J. I should have though. – TheoryQuest1 May 28 '15 at 6:35

If $n=p_1p_2p_3$ is composite, where $p_1,p_2,p_3$ are three distinct prime factors, and $p_1,p_2,p_3$ are given, then the problem can be solved in polynomial time. In particular, in this case, there are only 8 square roots of $q$ (modulo $n$), and you can enumerate them all and check whether any of them are in the range $[0,c)$.
Details and justification: you can use the Chinese remainder theorem. Let $x_1$ be one of the two square roots of $q$ modulo $p_1$, i.e., it satisfies $x_1^2 \equiv q \pmod{p_1}$. (Then the other square root is $-x_1$.) Similarly, let $x_2$ be a square root modulo $p_2$ and $x_3$ a square root modulo $p_3$. Then you can find a square root modulo $n$ by using the Chinese remainder theorem to find the unique solution to $x \equiv x_1 \pmod{p_1}$, $x \equiv x_2 \pmod{p_2}$, $x \equiv x_3 \pmod{p_3}$. In general, you can look for $x$ to be $x_1$ or $-x_1$ mod $p_1$, and $x_2$ or $-x_2$ mod $p_2$, and $x_3$ or $-x_3$ mod $p_3$; each of those $2 \times 2 \times 2 = 8$ combinations gives a different square root of $q$ modulo $n$. You can find $x_1,x_2,x_3$ in randomized polynomial time, and the CRT computation can be done in polynomial time, so you can enumerate all square roots modulo $n$ in polynomial time.
This same argument generalizes to any case where the number of prime factors of $n$ is constant, and where those prime factors are given in advance. However, when the number of prime factors is unlimited, this line of argument doesn't work, so this won't work for general $n$.
• Without further qualification, “polynomial time” means “deterministic polynomial time”. The only known efficient algorithms for computing square roots modulo primes are randomized. The assumption (which, more specifically, is the Riemann hypothesis for $L$-functions of quadratic Dirichlet characters) is used to derandomize the algorithm (see e.g. en.wikipedia.org/wiki/…). – Emil Jeřábek supports Monica Jun 13 '17 at 12:59