1
$\begingroup$

Last month, I asked whether there is an efficient algorithm for finding the square root modulo a prime power here: Is there an efficient algorithm for finding a square root modulo a prime power?

Now, let's say I am given a positive integer n and I know its factors. A paper by Manders and Adleman says that finding the square root of a number $\alpha$ modulo n is NP-complete, even if the factors of n are known.

But suppose that $n=p_1^{e_1} p_2^{e_2} ... p_m^{e_m}$. If I can efficiently compute the square root of $\alpha$ mod $p_i^{e_i}$ for each $i$, why can't I use the Chinese remainder Theorem to get the square root of $\alpha$ modulo n efficiently?

In fact, I tried it for $\alpha=862$ and $n=931=7^2 19$. In this case, 29=862 mod 49 and 7 = 862 mod 19. The square roots are 15,34 and 8,11 respectively. For each of these combinations, I got 407, 505, 426, 524 as square roots of 862 mod 931.

I certainly don't believe that P=NP. So what is wrong with this general strategy?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ There's nothing wrong with this general strategy. You can use the Chinese remainder theorem. What is the paper by Manders and Adelman, and is that really what it says? I vaguely remember a result that I believe says the problem of finding a square root of $\alpha$ modulo $n$ where the square root is between $0$ and $m$ is NP-complete. $\endgroup$
    – Peter Shor
    Feb 9, 2011 at 22:29
  • $\begingroup$ Clearly, the CRT argument shows that if the factorization of $n$ is known, the running time to compute a square root modulo $n$ depends on the size of the largest prime divisor of $n$. Since $n$ can be prime, the complexity of finding square roots modulo $n$ with known factorization of $n$ is asymptotically the same as for finding square roots modulo primes. So if you can show (or if the paper you mention shows this) that finding square roots in $\IF_p$ is NP complete, then so is your problem of finding square roots with known factorization of the modulus. $\endgroup$
    – felix
    Feb 9, 2011 at 22:35
  • $\begingroup$ The name of the paper by Manders and Adelman is "NP-complete decision problems for quadratic polynomials". It says "The problem of accepting the set of quadratic congruences (in a standard encoding) $x^2= \alpha$ mod $\beta$ with solutions satisfying $0\leq x \leq \gamma$, $\alpha,\beta,\gamma \in \omega$ is NP-complete, even if the prime factorization of $\beta$ and all solutions to the congruence modulo all prime powers occurring in this factorization are given gratis." $\endgroup$
    – Craig Feinstein
    Feb 9, 2011 at 22:37
  • 5
    $\begingroup$ @Craig: It's that pesky specification "$0\leq x \leq \gamma$" which is inducing NP-completeness. $\endgroup$
    – David Hansen
    Feb 9, 2011 at 22:41
  • 2
    $\begingroup$ So I guess what they are saying is that if you have integers $a_i$ and $b_i$, $i=1,\dots,t$, and you want to know whether $x\equiv a_i{\rm\ or\ }b_i\pmod{m_i}$, $i=1,\dots,t$ has a solution with $x$ in some given range (say, $0\le x\le\gamma$), no one knows a better way than using the Chinese Remainder Theorem $2^t$ times, once for each choice between an $a_i$ and a $b_i$. $\endgroup$
    – Gerry Myerson
    Feb 9, 2011 at 22:56

1 Answer 1

Reset to default
1
$\begingroup$

I see my mistake now. I interpreted the paper by Manders and Adelman wrong. I thought that the theorem in their paper implied that finding a square root is NP-complete, but this not true.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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