Chinese Remainder Theorem

Math for CS · Axiom Academy

LESSON Chinese Remainder Theorem A 1,800-year-old algorithm that still powers modern cryptography. 1. The Setup: Systems of Congruences A congruence means " x leaves remainder a when divided by n ." A system of congruences is several such conditions all required to hold simultaneously. The pairwise-coprime condition is essential. Without it, a system can have no solution at all (e.g. and are inconsistent because both moduli share the factor 2). The two claims hidden in this statement are equally important: Existence. A solution exists no matter which residues a_i we pick. Uniqueness mod N . Any two solutions differ by a multiple of N . So among there is exactly one solution. 3. Constructive Proof (the Algorithm) The proof gives an explicit recipe for building x . Define So N_i is the product of all the moduli except n_i . Because the n_i are pairwise coprime, , which means N_i has a multiplicative inverse modulo n_i . Call it M_i : 4. Worked Example: Sun Tzu's Puzzle Solve Sun Tzu's original system: Step 1. Compute N and the partial products N_i : Step 3. Plug into the formula: And , so the unique answer in is x = 23 . Quick check: , , . 5. Why CRT Matters: RSA Decryption Speedup RSA decryption requires computing where n = pq and d is huge — a 2048-bit RSA key has d about 2048 bits long. Doing that exponentiation directly is expensive. CRT to the rescue. Instead of working modulo the giant n , do two smaller exponentiations:

This is the written version of the interactive lesson above. See the full Math for CS course.