0
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Nov 13, 2015 at 13:50
  • $\begingroup$ Your title asks about squares, your first paragraph, without the specific question, mentions squares. Then, you get to the question and you ask for square roots. Help people help you. One thing you should do is ask your question first. $\endgroup$
    – Thomas Andrews
    Nov 13, 2015 at 13:54
  • $\begingroup$ 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$. $\endgroup$
    – TonyK
    Nov 13, 2015 at 14:19

2 Answers 2

Reset to default
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – TonyK
    Nov 13, 2015 at 14:17
  • $\begingroup$ 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! $\endgroup$
    – Bernard
    Nov 13, 2015 at 14:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.