##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
The Chinese Remainder Theorem (CRT) is a fundamental result in number theory. It states that if you know the remainders of an integer when divided by several pairwise coprime numbers, you can uniquely determine the remainder when divided by their product.
Historical context: The theorem appears in the 3rd century Chinese text Sunzi Suanjing, where it was used to solve problems about counting soldiers.
Problem statement: Given a system of congruences:
Apply what you learned by solving the practice problem for Chinese Remainder Theorem.
Go to Practice Problemwhere for all , there exists a unique solution modulo .
The classical CRT proof gives an explicit formula for the solution.
Setup:
The solution:
Why it works:
So the -th term contributes modulo and 0 modulo all other .
A simpler approach combines equations one at a time.
Algorithm:
function solve_crt(equations):
x = equations[0].remainder
mod = equations[0].modulus
for each (a, m) in equations[1:]:
// Find k such that: x + k * mod ≡ a (mod m)
// k ≡ (a - x) * mod^(-1) (mod m)
inv = modular_inverse(mod, m)
k = ((a - x) * inv) mod m
if k < 0: k += m
x = x + k * mod
mod = mod * m
x = x mod mod
return x
Why it works: After processing the first equations, satisfies all of them modulo . Since all moduli are coprime, this LCM is just their product.
To find the modular inverse, we use the Extended Euclidean Algorithm.
Extended GCD: Given and , find such that .
function extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
(g, x, y) = extended_gcd(b, a mod b)
return (g, y, x - (a / b) * y)
Modular inverse: If , then:
So (reduced mod ) is the modular inverse of mod .
function modular_inverse(a, m):
(g, x, _) = extended_gcd(a, m)
if g != 1: error("No inverse")
return ((x mod m) + m) mod m
1. RSA Cryptography
The RSA decryption uses CRT to speed up computation. Instead of computing directly, compute:
Then combine using CRT. This is about 4x faster.
2. Solving modular equations
To solve where :
3. Hash functions
Some hash functions use CRT to combine multiple smaller hashes.
Complexity: