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?
Best Answer
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.