2
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek supports Monica Jun 19 '15 at 17:32
  • $\begingroup$ Good point, @EmilJeřábek -- thank you! $\endgroup$ – D.W. Jun 19 '15 at 17:37
  • $\begingroup$ 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? $\endgroup$ – TheoryQuest1 Aug 27 '16 at 8:10
  • 2
    $\begingroup$ 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/…). $\endgroup$ – Emil Jeřábek supports Monica Jun 13 '17 at 12:59

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.