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?](https://mathoverflow.net/questions/52081/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?



Finding the square root modulo n, when the factors of n are known
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.


