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

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.