04d-chinese-remainder-theorem.ipynb

Kernel: SageMath 10.5

The Chinese Remainder Theorem

Module 04d | Number Theory and RSA

One equation is a constraint. Two simultaneous equations are a superpower.

Question: A number leaves remainder 2 when divided by 3 and remainder 3 when divided by 5. What is the number? Is there exactly one answer, or could there be many?

This puzzle is over 1,500 years old, it appears in the 3rd-century Chinese text Sunzi Suanjing. The answer unlocks one of the most useful theorems in all of cryptography: a way to split a hard problem into easier pieces, solve each piece separately, and then glue the solutions back together.

Objectives

By the end of this notebook you will be able to:

1. Solve systems of simultaneous congruences by hand and with SageMath's CRT() and CRT_list()

2. Construct the CRT solution using the extended GCD (connecting back to notebook 04b)

3. Explain the CRT isomorphism $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ and verify it preserves both addition and multiplication

4. Apply CRT to RSA decryption (RSA-CRT speedup) and recognize its role in Pohlig-Hellman

Prerequisites

• Completion of The Extended Euclidean Algorithm, you will need xgcd() and Bezout's identity

• Completion of Euler's Totient and Fermat's Theorem, you will need euler_phi() and power_mod()

• Comfort with modular arithmetic from Module 01

The Puzzle: Solving Two Congruences at Once

Let's start with the motivating question. We want to find $x$ such that: $$x \equiv 2 \pmod{3} \qquad \text{and} \qquad x \equiv 3 \pmod{5}$$

The brute-force approach: just try numbers until both conditions are satisfied.

# Brute-force: try all x from 0 to 14 (= 3*5 - 1)
for x in range(15):
    if x % 3 == 2 and x % 5 == 3:
        print(f'Found it: x = {x}')
        print(f'  Check: {x} mod 3 = {x % 3}, {x} mod 5 = {x % 5}')

# Let's also check: are there any OTHER solutions in 0..29?
print('\nAll solutions in 0..29:')
for x in range(30):
    if x % 3 == 2 and x % 5 == 3:
        print(f'  x = {x}')

We found $x = 8$ in the range $\{0, \ldots, 14\}$, and $x = 23$ in $\{15, \ldots, 29\}$. Notice that $23 = 8 + 15 = 8 + 3 \times 5$. The solutions are $8, 23, 38, 53, \ldots$, they form a single residue class modulo $15$.

So the answer to our motivating question is: the number is 8 (mod 15), and the answer is unique modulo 15.

This is not a coincidence. It is a theorem.

The Chinese Remainder Theorem (Statement)

Theorem (CRT). Let $m$ and $n$ be positive integers with $\gcd(m, n) = 1$. For any integers $a$ and $b$, the system

$$x \equiv a \pmod{m}, \qquad x \equiv b \pmod{n}$$

has a unique solution modulo $mn$.

The two key ingredients:

1. Existence, a solution always exists

2. Uniqueness, there is exactly one solution in $\{0, 1, \ldots, mn - 1\}$

Misconception alert: "CRT works for any pair of moduli." No! The moduli must be coprime ($\gcd(m, n) = 1$). If $\gcd(m, n) > 1$, the system may have no solution (e.g., $x \equiv 1 \pmod{4}$ and $x \equiv 0 \pmod{6}$) or multiple solutions modulo $mn$. We will see a concrete failure case below.

# What happens when gcd(m, n) > 1?
# Try: x ≡ 1 (mod 4) and x ≡ 0 (mod 6).  gcd(4, 6) = 2
print(f'gcd(4, 6) = {gcd(4, 6)} . NOT coprime!\n')

solutions = [x for x in range(24) if x % 4 == 1 and x % 6 == 0]
print(f'Solutions in 0..23: {solutions}')
print('No solution exists! CRT requires coprime moduli.\n')

# Another failure: x ≡ 0 (mod 4) and x ≡ 2 (mod 6).  gcd(4,6)=2
solutions2 = [x for x in range(24) if x % 4 == 0 and x % 6 == 2]
print(f'x ≡ 0 (mod 4), x ≡ 2 (mod 6): solutions in 0..23 = {solutions2}')
print('Two solutions mod 24, uniqueness fails too.')

Constructing the Solution with Extended GCD

Bridge from 04b: In the extended Euclidean algorithm notebook, we learned that when $\gcd(m, n) = 1$, Bezout's identity gives us integers $s, t$ such that $$s \cdot m + t \cdot n = 1.$$

This is exactly what we need to construct the CRT solution. Here is the recipe:

1. Compute $s, t$ with xgcd(m, n) so that $sm + tn = 1$.

2. The solution is: $x = a \cdot t \cdot n + b \cdot s \cdot m \pmod{mn}$.

Why does this work? Reduce $x$ modulo $m$: since $sm + tn = 1$, we have $tn \equiv 1 \pmod{m}$, so $x \equiv a \cdot 1 + b \cdot 0 = a \pmod{m}$. Similarly, $x \equiv b \pmod{n}$.

Checkpoint: Before running the next cell, try the construction by hand for $m = 3$, $n = 5$, $a = 2$, $b = 3$. You need $s$ and $t$ such that $3s + 5t = 1$. Can you find $s = 2, t = -1$? Then $x = 2 \cdot (-1) \cdot 5 + 3 \cdot 2 \cdot 3 = -10 + 18 = 8$.

# CRT construction from extended GCD
m, n = 3, 5
a, b = 2, 3

# Step 1: Bezout coefficients
g, s, t = xgcd(m, n)
print(f'xgcd({m}, {n}) = ({g}, {s}, {t})')
print(f'Verify Bezout: {s}*{m} + {t}*{n} = {s*m + t*n}\n')

# Step 2: Construct the solution
x = (a * t * n + b * s * m) % (m * n)
print(f'x = {a}*{t}*{n} + {b}*{s}*{m} = {a*t*n + b*s*m} ≡ {x} (mod {m*n})')
print(f'Check: {x} mod {m} = {x % m} (want {a})')
print(f'Check: {x} mod {n} = {x % n} (want {b})')

SageMath's Built-in CRT

SageMath provides CRT(a, b, m, n) for two congruences and CRT_list(remainders, moduli) for any number of simultaneous congruences. Let's verify our hand computation and then try a larger example.

# Two-congruence CRT
x = CRT(2, 3, 3, 5)
print(f'CRT(2, 3, 3, 5) = {x}  (solution mod {3*5})')
print(f'Check: {x} mod 3 = {x%3}, {x} mod 5 = {x%5}\n')

# Multi-congruence CRT: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
x = CRT_list([2, 3, 2], [3, 5, 7])
print(f'CRT_list([2,3,2], [3,5,7]) = {x}  (solution mod {3*5*7})')
print(f'Check: {x} mod 3 = {x%3}, {x} mod 5 = {x%5}, {x} mod 7 = {x%7}')

Generalization to Multiple Moduli

The CRT generalizes naturally. Given pairwise coprime moduli $m_1, m_2, \ldots, m_k$ (meaning $\gcd(m_i, m_j) = 1$ for all $i \neq j$), the system

$$x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}$$

has a unique solution modulo $M = m_1 m_2 \cdots m_k$.

Misconception alert: "Pairwise coprime" is stronger than just "all share no common factor." For example, $\{6, 10, 15\}$ have $\gcd(6, 10, 15) = 1$, but they are not pairwise coprime since $\gcd(6, 10) = 2$. CRT would not apply to this triple.

# Pairwise coprime vs. just coprime overall

mods = [6, 10, 15]
print(f'Moduli: {mods}')
print(f'gcd of all three: {gcd(mods)}')  # = 1
for a, b in Combinations(mods, 2):
    print(f'  gcd({a}, {b}) = {gcd(a, b)}')  # some > 1
print('Not pairwise coprime, CRT does not apply!\n')

# A proper pairwise coprime set
mods = [7, 11, 13]
print(f'Moduli: {mods}')
for a, b in Combinations(mods, 2):
    print(f'  gcd({a}, {b}) = {gcd(a, b)}')
print(f'Pairwise coprime! CRT gives unique solution mod {prod(mods)}.')

CRT as an Isomorphism

The CRT is much more than a system-solver. It tells us that two apparently different algebraic structures are the same thing in disguise:

$$\mathbb{Z}/mn\mathbb{Z} \;\cong\; \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \qquad \text{(when } \gcd(m, n) = 1\text{)}$$

The isomorphism sends $x \bmod mn$ to the pair $(x \bmod m, \; x \bmod n)$. This is a ring isomorphism, it preserves both addition and multiplication.

Let's build the complete mapping for $\mathbb{Z}/15\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z}$.

# The CRT isomorphism: Z/15Z → Z/3Z × Z/5Z
m, n = 3, 5
print(f'Z/{m*n}Z  →  Z/{m}Z × Z/{n}Z')
print(f'{"-"*35}')
for x in range(m * n):
    print(f'  {x:2d}  ↦  ({x % m}, {x % n})')

print(f'\nEvery pair (a, b) with 0 ≤ a < {m} and 0 ≤ b < {n} appears exactly once.')
print(f'This confirms the map is a BIJECTION: {m*n} elements ↔ {m}×{n} = {m*n} pairs.')

Verifying: It Preserves Addition AND Multiplication

A ring isomorphism must satisfy $\phi(x + y) = \phi(x) + \phi(y)$ and $\phi(x \cdot y) = \phi(x) \cdot \phi(y)$, where operations on the left happen in $\mathbb{Z}/mn\mathbb{Z}$ and operations on the right happen component-wise in $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$.

Checkpoint: Pick any two elements, say $x = 7$ and $y = 11$ in $\mathbb{Z}/15\mathbb{Z}$. Predict: what is $\phi(7 + 11) = \phi(3)$? Does it equal $\phi(7) + \phi(11)$ component-wise?

# Verify the ring isomorphism for ALL pairs in Z/15Z
m, n = 3, 5
mn = m * n
phi = lambda x: (x % m, x % n)  # the CRT map

add_ok = 0
mul_ok = 0
total = 0

for x in range(mn):
    for y in range(mn):
        total += 1
        # Addition check: phi(x+y) == phi(x) + phi(y)  (component-wise)
        lhs_add = phi((x + y) % mn)
        rhs_add = ((phi(x)[0] + phi(y)[0]) % m, (phi(x)[1] + phi(y)[1]) % n)
        if lhs_add == rhs_add:
            add_ok += 1

        # Multiplication check: phi(x*y) == phi(x) * phi(y)
        lhs_mul = phi((x * y) % mn)
        rhs_mul = ((phi(x)[0] * phi(y)[0]) % m, (phi(x)[1] * phi(y)[1]) % n)
        if lhs_mul == rhs_mul:
            mul_ok += 1

print(f'Checked {total} pairs in Z/{mn}Z:')
print(f'  Addition preserved:       {add_ok}/{total}')
print(f'  Multiplication preserved: {mul_ok}/{total}')
print(f'\nRing isomorphism confirmed!' if add_ok == total and mul_ok == total else '\nSomething went wrong!')

Visualizing: Addition Tables Match

To make the isomorphism tangible, let's display the addition table of $\mathbb{Z}/15\mathbb{Z}$ side-by-side with the component-wise addition in $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z}$. We'll use a small subset to keep it readable.

# Side-by-side: addition in Z/15Z vs. Z/3Z × Z/5Z
m, n = 3, 5
mn = m * n
elements = [0, 1, 4, 7, 11, 13]  # a sample subset

print('Addition in Z/15Z              Addition in Z/3Z × Z/5Z')
print('='*55)
for x in elements:
    for y in elements:
        z15 = (x + y) % mn
        # Component-wise addition
        pair_x = (x % m, x % n)
        pair_y = (y % m, y % n)
        pair_z = ((pair_x[0]+pair_y[0]) % m, (pair_x[1]+pair_y[1]) % n)
        # Inverse map: pair_z back to Z/15Z
        z_back = CRT(pair_z[0], pair_z[1], m, n)
        match = '✓' if z15 == z_back else '✗'
        print(f'  {x:2d} + {y:2d} = {z15:2d}    '
              f'{pair_x} + {pair_y} = {pair_z} → {z_back:2d}  {match}')
    print()

Application: RSA-CRT (4x Speedup)

Crypto foreshadowing: In RSA, we compute $c^d \bmod n$ where $n = pq$. Since $\gcd(p, q) = 1$, the CRT isomorphism tells us:

$$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z}$$

Instead of one expensive exponentiation mod $n$ (a large number), we can compute:

1. $m_p = c^{d \bmod (p-1)} \bmod p$, exponentiation mod $p$ (half the bits!)

2. $m_q = c^{d \bmod (q-1)} \bmod q$, exponentiation mod $q$ (half the bits!)

3. Combine: $m = \text{CRT}(m_p, m_q, p, q)$

Since modular exponentiation cost is roughly cubic in the number of bits, halving the modulus size gives roughly a $(1/2)^3 + (1/2)^3 = 1/4$ cost, a 4x speedup.

Let's see it in action with a toy RSA example (and then measure a real speedup).

# RSA-CRT demonstration
# Step 1: Generate RSA keys
p = random_prime(2^512)
q = random_prime(2^512)
n = p * q
phi_n = (p - 1) * (q - 1)
e = 65537
d = inverse_mod(e, phi_n)

# A message
message = 123456789
c = power_mod(message, e, n)  # encrypt

# Standard RSA decryption
m_standard = power_mod(c, d, n)
print(f'Standard RSA decryption: {m_standard}')

# RSA-CRT decryption
d_p = d % (p - 1)   # d mod (p-1)
d_q = d % (q - 1)   # d mod (q-1)
m_p = power_mod(c, d_p, p)  # decrypt mod p
m_q = power_mod(c, d_q, q)  # decrypt mod q
m_crt = CRT(m_p, m_q, p, q) # combine with CRT
print(f'RSA-CRT decryption:     {m_crt}')
print(f'Results match: {m_standard == m_crt}')

# Timing comparison: standard vs. CRT

# Use larger primes for a visible timing difference
p = random_prime(2^1024)
q = random_prime(2^1024)
n = p * q
phi_n = (p - 1) * (q - 1)
e = 65537
d = inverse_mod(e, phi_n)
message = 42
c = power_mod(message, e, n)

# Standard decryption
trials = 50
start = walltime()
for _ in range(trials):
    m_std = power_mod(c, d, n)
elapsed_std = walltime() - start

# CRT decryption
d_p = d % (p - 1)
d_q = d % (q - 1)
start = walltime()
for _ in range(trials):
    m_p = power_mod(c, d_p, p)
    m_q = power_mod(c, d_q, q)
    m_crt = CRT(m_p, m_q, p, q)
elapsed_crt = walltime() - start

print(f'Standard: {elapsed_std:.4f}s for {trials} decryptions')
print(f'RSA-CRT:  {elapsed_crt:.4f}s for {trials} decryptions')
print(f'Speedup:  {elapsed_std/elapsed_crt:.1f}x')
print(f'Correct:  {m_std == m_crt}')

Connection: CRT in Pohlig-Hellman

Bridge to Module 06 (DLP/DH): The Pohlig-Hellman algorithm solves the discrete logarithm problem in a group of composite order $n = p_1^{e_1} \cdot p_2^{e_2} \cdots$ by:

1. Solving the DLP in each prime-power subgroup of order $p_i^{e_i}$ (much easier!)

2. Combining the results with CRT to recover the full discrete log modulo $n$

This is the same "split and recombine" strategy as RSA-CRT, but applied to a different problem. The CRT is the glue.

Here is a miniature example: solve $3^x \equiv 13 \pmod{35}$ where $|\langle 3 \rangle| = 12 = 4 \times 3$.

# Miniature Pohlig-Hellman using CRT
# Solve 2^x ≡ 7 (mod 29).  Order of 2 mod 29 is 28 = 4 × 7.
G = Integers(29)
g = G(2)
h = G(7)
n = g.multiplicative_order()
print(f'g = {g}, h = {h}, order = {n}, factored = {factor(n)}\n')

# Subproblem 1: solve in subgroup of order 4
# Lift to subgroup: g1 = g^(n/4), h1 = h^(n/4)
g1 = g^(n // 4)
h1 = h^(n // 4)
# Brute-force DLP in small subgroup
x1 = discrete_log(h1, g1)
print(f'Subgroup order 4: {g1}^x1 = {h1}, x1 = {x1}')

# Subproblem 2: solve in subgroup of order 7
g2 = g^(n // 7)
h2 = h^(n // 7)
x2 = discrete_log(h2, g2)
print(f'Subgroup order 7: {g2}^x2 = {h2}, x2 = {x2}')

# Combine with CRT: x ≡ x1 (mod 4), x ≡ x2 (mod 7)
x = CRT(x1, x2, 4, 7)
print(f'\nCRT gives x = {x} (mod {n})')
print(f'Verify: {g}^{x} mod 29 = {power_mod(2, x, 29)} (want {h})')

Exercises

Exercise 1 (Fully Worked)

Problem: Find $x$ such that $x \equiv 3 \pmod{7}$ and $x \equiv 5 \pmod{11}$.

Solution:

1. Check: $\gcd(7, 11) = 1$ (both prime, so coprime). CRT applies.

2. Find Bezout coefficients: $7s + 11t = 1$.

3. Construct: $x = a \cdot t \cdot n + b \cdot s \cdot m \pmod{mn}$.

# Exercise 1: Fully worked solution
m, n = 7, 11
a, b = 3, 5

# Step 1: verify coprimality
print(f'gcd({m}, {n}) = {gcd(m, n)}, coprime, CRT applies.\n')

# Step 2: Bezout coefficients
g, s, t = xgcd(m, n)
print(f'Bezout: {s}*{m} + {t}*{n} = {s*m + t*n}\n')

# Step 3: construct the solution
x_manual = (a * t * n + b * s * m) % (m * n)
print(f'Manual construction: x = {a}*{t}*{n} + {b}*{s}*{m} = {a*t*n + b*s*m} ≡ {x_manual} (mod {m*n})')

# Step 4: verify
print(f'Check: {x_manual} mod {m} = {x_manual % m} (want {a})')
print(f'Check: {x_manual} mod {n} = {x_manual % n} (want {b})')

# Cross-check with SageMath
x_sage = CRT(a, b, m, n)
print(f'\nSageMath CRT: {x_sage}')
print(f'Matches manual: {x_manual == x_sage}')

Exercise 2 (Guided with TODOs)

Problem: Solve the system $x \equiv 1 \pmod{5}$, $x \equiv 2 \pmod{7}$, $x \equiv 3 \pmod{11}$.

Steps:

1. Verify the moduli are pairwise coprime.

2. Use CRT_list() to find the solution.

3. Verify by checking each congruence.

4. What is the solution modulo? (What is $5 \times 7 \times 11$?)

# Exercise 2: Fill in the TODOs
remainders = [1, 2, 3]
moduli = [5, 7, 11]

# TODO 1: Check pairwise coprimality
# Hint: use gcd(moduli[i], moduli[j]) for all pairs i < j
for a, b in Combinations(moduli, 2):
    pass  # TODO: print gcd(a, b) and check it equals 1

# TODO 2: Find the solution using CRT_list
# x = CRT_list(???, ???)

# TODO 3: Verify each congruence
# for r, m in zip(remainders, moduli):
#     print(f'{x} mod {m} = {x % m} (want {r})')

# TODO 4: What is the combined modulus?
# print(f'Solution is unique modulo {???}')

Exercise 3 (Independent)

Problem: Implement your own CRT solver from scratch (without using SageMath's CRT() or CRT_list()), using only xgcd().

Your function my_crt(a, b, m, n) should:

1. Check that $\gcd(m, n) = 1$ (raise an error if not)

2. Use xgcd() to find Bezout coefficients

3. Return the unique solution modulo $mn$

Then extend it to my_crt_list(remainders, moduli) that handles arbitrarily many congruences by applying the two-modulus version iteratively.

Test both functions against SageMath's built-in CRT() and CRT_list().

# Exercise 3: Your code here

def my_crt(a, b, m, n):
    """Solve x ≡ a (mod m), x ≡ b (mod n) using extended GCD."""
    # Your implementation here
    pass

def my_crt_list(remainders, moduli):
    """Solve a system of congruences using iterative CRT."""
    # Your implementation here
    pass

# Test your implementation:
# assert my_crt(2, 3, 3, 5) == CRT(2, 3, 3, 5)
# assert my_crt_list([2, 3, 2], [3, 5, 7]) == CRT_list([2, 3, 2], [3, 5, 7])
# print('All tests passed!')

Summary

Concept	Key idea
CRT existence and uniqueness	When $\gcd(m, n) = 1$, the system $x \equiv a \pmod{m}$, $x \equiv b \pmod{n}$ has exactly one solution modulo $mn$
Construction via extended GCD	Bezout coefficients from xgcd() (notebook 04b) directly give the CRT solution formula
Ring isomorphism	$\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ preserves both addition and multiplication, which is why RSA can "split" computations
RSA-CRT speedup	Decrypt mod $p$ and mod $q$ separately, then combine. Each half-size exponentiation is roughly 8x cheaper, giving about a 4x speedup overall
Pohlig-Hellman connection	Solve the DLP in small prime-power subgroups, then recombine with CRT. The same "split and recombine" pattern

Crypto foreshadowing: In the next notebook, we'll generate RSA keys. The CRT isomorphism is why RSA works: the structure of $\mathbb{Z}/n\mathbb{Z}$ for $n = pq$ is secretly controlled by $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z}$, and only someone who knows $p$ and $q$ can exploit this.

Next: RSA Key Generation