# How to find all square roots of a number mod a product of primes.

How do you find the square root of a number mod a product of primes? I know that algorithms exist for finding the square root of a number mod a prime, such as tonelli-shanks, but I also know there must be an easier way to find the square roots mod pq where p and q are distinct primes.

The specific problem that I am trying to solve is "find all square roots of 1748 mod 11201. (Hint: 11201 = 103*107. 103 and 107 are both prime).

• There seems to be a disconnect between the last part of your Question and the title and opening paragraph. Finding "the square of a number" is not the same as finding the square root of a number. Please edit to resolve this inconsistency. Nov 13 '15 at 13:50
• Note that if you know $pq$ but you don't know $p$ and $q$, then finding a square root mod $pq$ is as hard as factorising $pq$. So really the only way to go is to find the square roots separately, mod $p$ and mod $q$. Nov 13 '15 at 14:19
Tonelli-Shanks is not required in the present case. You have $$\begin{cases} 1748\mod103\equiv100&\text{hence}\quad1748\equiv\color{red}{\pm10}\mod103,\\ 1748\mod107\equiv36&\text{hence}\quad1748\equiv\color{cyan}{\pm6}\mod107. \end{cases}$$
Now the extended euclidean algorithm yields this Bézout's relation: $\;26\cdot 107-27\cdot103=1$, whence by the Chinese remainder isomorphism the square roots of $1748$ : $$\color{red}{\pm10}\cdot26\cdot107\color{cyan}{\pm6}\cdot27\cdot103.$$
• One of those sixes in the last line should be ten, I think. Also, why $\pm x \mp y$? To me, this means $x-y$ or $-x+y$. Simply $\pm x \pm y$ is clearer. Nov 13 '15 at 14:17
• For the first point, you're right, I'll correct the typo. Second point, it's an old reflex, because of the $-$ sign in Bézout' identity, but it's relevant here. Thanks for point these problems! Nov 13 '15 at 14:22
You need to find all square roots of $1748$ mod $103$ and $107$ respectively (using Tonelli-Shanks) and then take back each pair mod $11201$ using the Chinese isomorphism. You need some calculus to find the explicit reciprocal of the Chinese isomorphism.