New tool: the CRT Demo page shows the Chinese Remainder Theorem as two meshed gears (mod $m$ and mod $n$) turning a big mod $mn$ dial, along with the table from class. Try it with $m$ and $n$ coprime, and then with $m$ and $n$ sharing a factor.

Relevant Textbook Sections:

3.3 (Computing modular inverses), 3.4 (Sunzi’s Theorem (Chinese Remainder Theorem)).

To Do:

1. Find the inverse of $35$ modulo $61$. Use the extended Euclidean algorithm. Verify your answer by multiplying out.
2. Try out this Chinese Remainder Theorem problem, by hand: $x \equiv 3 \pmod{244}$ and $x \equiv 17 \pmod{495}$. Show all the steps of the process, including the extended Euclidean algorithm. You can use the computer to do modular arithmetic for you (e.g. multiplying things if needed), but show the steps as if doing it by hand.
3. Use any remaining time to do extra examples of CRT problems (you can make up your own by just putting in whatever numbers you want, as long as the moduli are coprime, and you can always check your answer by plugging it back into the original equations). The CRT Demo page can solve small ones too (moduli up to 20), so you can check your answers there.
4. (AI suggestion) Sunzi’s original problem (c. 3rd–5th century): “There are certain things whose number is unknown. Counted by threes, two are left over; by fives, three are left over; by sevens, two are left over. How many things are there?” Solve it using CRT with three congruences.
5. (AI suggestion) When the moduli are not coprime, CRT can fail. Does $x \equiv 3 \pmod 6$, $x \equiv 5 \pmod 8$ have a solution? What about $x \equiv 1 \pmod 6$, $x \equiv 2 \pmod 8$? Explain when such a system has a solution, and how many solutions it has modulo $24$.
6. (AI suggestion) Another way to invert modulo a prime: by Fermat’s little theorem, $a^{-1} \equiv a^{p-2} \pmod p$. Compute $35^{59} \bmod 61$ and compare with problem 1. Which method would you rather use for a 300-digit prime, and why? Which method still works modulo a composite $n$?
7. (AI suggestion) CRT speeds up RSA. Alice’s key from the last daily post is $n = 3233 = 61 \cdot 53$, $e = 17$, $d = 2753$, and she receives the ciphertext $c = 2790$. Instead of computing $c^{d} \bmod 3233$ directly, compute $c^{d} \bmod 61$ and $c^{d} \bmod 53$ (why may you reduce the exponent $d$ modulo $60$ and modulo $52$ respectively?), and then combine the two answers with CRT. Check your answer against the direct computation. Why is this faster?
8. (AI suggestion) Håstad’s broadcast attack. Bob sends the same message $m$ to three friends, all using $e = 3$, with public moduli $n_1 = 55$, $n_2 = 391$, $n_3 = 1189$. Eve sees the ciphertexts $c_1 = 3$, $c_2 = 189$, $c_3 = 370$. Use CRT to find $X$ modulo $n_1 n_2 n_3$ with $X \equiv c_i \pmod{n_i}$ for each $i$. Explain why $X$ must equal $m^3$ exactly (as an integer, not just modulo something), and recover $m$. What does this suggest about sending the same message to several people with a small $e$?