# 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? Commented May 28, 2015 at 5:23
• I did not have a look at the proof but know the from from G&J. I should have though. Commented May 28, 2015 at 6:35

It can be solved in randomized polynomial time, so it's not NP-complete (unless RP=NP, which is considered unlikely).

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

• When you write polynomial time, you mean randomized polynomial time. Likewise, P=NP should read ZPP=NP. There are no known deterministic polynomial time algorithms to compute square roots modulo arbitrary primes. Commented Jun 19, 2015 at 17:32
• Good point, @EmilJeřábek -- thank you!
– D.W.
Commented Jun 19, 2015 at 17:37
• This is more of a clarification request: Garey and Johnson mentions "assuming the Extended Riemann Hypothesis, the problem is solvable in polynomial time when n is a prime ". Query: Why do we need the additional ERH assumption for this. Isn't the assumption redundant? Commented Aug 27, 2016 at 8:10
• 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/…). Commented Jun 13, 2017 at 12:59