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).
Best Answer
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.$$