2.4 The Chinese Remainder Theorem

The Chinese Remainder Theorem is a powerful tool in number theory, allowing us to solve systems of congruences with coprime moduli. It's like a mathematical puzzle solver, finding unique solutions to complex equations by breaking them into simpler parts.

This theorem connects to the broader study of additive number theory by providing a way to work with modular arithmetic efficiently. It's essential for various applications, from cryptography to computer science, showcasing how fundamental number theory concepts can solve real-world problems.

Chinese Remainder Theorem

Statement and Proof

• States if $n_1, n_2, ..., n_k$ are pairwise coprime positive integers and $a_1, a_2, ..., a_k$ are any integers, then the system of simultaneous congruences $x \equiv a_1 \pmod {n_1}, x \equiv a_2 \pmod {n_2}, ..., x \equiv a_k \pmod {n_k}$ has a unique solution modulo $N = n_1 \times n_2 \times ... \times n_k$
• Proves the theorem by constructing a solution using the following steps:
  • Let $N = n_1 \times n_2 \times ... \times n_k$ and $N_i = N / n_i$ for each $i$
  • Find integers $y_i$ such that $N_i \times y_i \equiv 1 \pmod {n_i}$ using the extended Euclidean algorithm
  • The solution is given by $x = a_1 \times N_1 \times y_1 + a_2 \times N_2 \times y_2 + ... + a_k \times N_k \times y_k$
• Proves the uniqueness of the solution by assuming two solutions $x_1$ and $x_2$ and showing that $x_1 \equiv x_2 \pmod N$

Ring Isomorphisms

• Establishes an isomorphism between the ring $\mathbb{Z}/N\mathbb{Z}$ and the product of rings $\mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z} \times ... \times \mathbb{Z}/n_k\mathbb{Z}$, where $N = n_1 \times n_2 \times ... \times n_k$ and $n_1, n_2, ..., n_k$ are pairwise coprime
• The isomorphism is given by the map $\phi: \mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z} \times ... \times \mathbb{Z}/n_k\mathbb{Z}$ defined by $\phi(x \bmod N) = (x \bmod n_1, x \bmod n_2, ..., x \bmod n_k)$
• The inverse map $\phi^{-1}: \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z} \times ... \times \mathbb{Z}/n_k\mathbb{Z} \to \mathbb{Z}/N\mathbb{Z}$ is given by the Chinese Remainder Theorem, which constructs a unique element $x \in \mathbb{Z}/N\mathbb{Z}$ from its residues $(a_1, a_2, ..., a_k)$ modulo $n_1, n_2, ..., n_k$
• Allows for the reduction of computations in $\mathbb{Z}/N\mathbb{Z}$ to computations in the smaller rings $\mathbb{Z}/n_1\mathbb{Z}, \mathbb{Z}/n_2\mathbb{Z}, ..., \mathbb{Z}/n_k\mathbb{Z}$, simplifying calculations and improving efficiency

Solving Linear Congruences

Application of the Chinese Remainder Theorem

• Used to solve systems of linear congruences of the form $x \equiv a_1 \pmod {n_1}, x \equiv a_2 \pmod {n_2}, ..., x \equiv a_k \pmod {n_k}$, where $n_1, n_2, ..., n_k$ are pairwise coprime
• To apply the theorem, follow these steps:
  • Check that the moduli $n_1, n_2, ..., n_k$ are pairwise coprime
  • Calculate $N = n_1 \times n_2 \times ... \times n_k$ and $N_i = N / n_i$ for each $i$
  • Find integers $y_i$ such that $N_i \times y_i \equiv 1 \pmod {n_i}$ using the extended Euclidean algorithm
  • Compute the solution $x = a_1 \times N_1 \times y_1 + a_2 \times N_2 \times y_2 + ... + a_k \times N_k \times y_k$
• The solution $x$ obtained is unique modulo $N$, ensuring a single solution to the system of congruences

Examples

• Solve the system of congruences: $x \equiv 2 \pmod 3, x \equiv 3 \pmod 5, x \equiv 2 \pmod 7$
  • Check that $3, 5, 7$ are pairwise coprime
  • Calculate $N = 3 \times 5 \times 7 = 105$, $N_1 = 35$, $N_2 = 21$, $N_3 = 15$
  • Find $y_1 = 2$, $y_2 = 1$, $y_3 = 1$ using the extended Euclidean algorithm
  • Compute the solution $x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 233$
  • The unique solution modulo $105$ is $23$
• Solve the system of congruences: $x \equiv 1 \pmod 4, x \equiv 2 \pmod 9, x \equiv 5 \pmod {11}$
  • Check that $4, 9, 11$ are pairwise coprime
  • Calculate $N = 4 \times 9 \times 11 = 396$, $N_1 = 99$, $N_2 = 44$, $N_3 = 36$
  • Find $y_1 = 3$, $y_2 = 5$, $y_3 = 4$ using the extended Euclidean algorithm
  • Compute the solution $x = 1 \times 99 \times 3 + 2 \times 44 \times 5 + 5 \times 36 \times 4 = 1417$
  • The unique solution modulo $396$ is $229$

Cryptographic Applications

RSA Cryptosystem

• The Chinese Remainder Theorem is used to speed up the decryption process in the RSA cryptosystem
• The modulus $N$ is the product of two large primes $p$ and $q$
• The decryption exponent $d$ is computed modulo $\phi(N) = (p-1)(q-1)$
• To decrypt a ciphertext $c$, compute $m_1 = c^d \bmod p$ and $m_2 = c^d \bmod q$, then use the Chinese Remainder Theorem to find the unique message $m$ modulo $N$
• This method is more efficient than directly computing $m = c^d \bmod N$, as it involves smaller modular exponentiations and the Chinese Remainder Theorem reconstruction

Paillier Cryptosystem

• The Chinese Remainder Theorem is used in the key generation process of the Paillier cryptosystem
• The public key is $N = pq$, where $p$ and $q$ are large primes
• The private key is $(\lambda, \mu)$, where $\lambda = \text{lcm}(p-1, q-1)$ and $\mu = (L(g^\lambda \bmod N^2))^{-1} \bmod N$, with $L(x) = (x-1)/N$ and $g$ chosen such that $\gcd(L(g^\lambda \bmod N^2), N) = 1$
• The Chinese Remainder Theorem is used to compute $\mu$ efficiently by working modulo $p$ and $q$ separately, reducing the complexity of the calculations
• This application of the Chinese Remainder Theorem enables the efficient generation of the private key in the Paillier cryptosystem