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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .