Question

Find four square roots of 2833 modulo 4189. (The modulus factors as 4189 = 59 · 71. Note that your four square roots should be distinct modulo 4189.)Hoffstein, Jeffrey. An Introduction to Mathematical Cryptography (Undergraduate Texts in Mathematics) (p. 112). Springer New York. Kindle Edition.

Answer 1

Answer:

Step-by-step explanation:

Let us proceed to find square roots of modulo 59 and 71:

$z^{2}$  ≡  2833  mod  59  ≡  1  mod 59                             (1)

$y^2$  ≡  2833  mod  71  ≡  64  mod 71                            (2)

By inspection, we find that $z$ = ± 1 and $y$ = ± 8 works

Now, using Chinese remainder to solve the simultaneous congruence,

$x$ ≡ $\left \{ {{1mod 59} \atop {8mod71}} \right.$

The first congruence yields

$x = 59t-1,$

Then putting this back into the second equation, we get

$59t-1$ ≡ $8$ $mod$ $71$ ⇒ $59t$ ≡ $9$ $mod$ $71$ ⇒ $354t$ ≡ $54$ $mod$ $71$

But

$354$ ≡ $-1$ $mod$ $71$ ;

Hence,

$-t$ ≡ $54$ $mod$ $71$ ⇒ $t$ ≡ $17$ $mod$ $71$

This shows that $x=59.17=1002$  is a third square root. From this, we immediately get the fourth square root, namely $-1002$ ≡ $3187$.

Note that the square roots:

$1002,3187,1712,2477$

are all distinct modulo 4189.