Chinese Remainder Theorem
By Sudheer Satyanarayana
Introduction
Continuing with the series of posts on number theory and cryptograpy, let us take a look at the Chinese Remainder Theorem.
Prereseqisites
- Modular arithmetic, especially modular inverses
- The Extended Euclidean Algorithm
The Chinese Remainder Theorem
The Chinese Remainder Theorem (CRT) provides a solution to a system of simultaneous congruences with different moduli. Here’s a step-by-step explanation:
Problem Setup
Suppose you have a system of congruences like this:
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
⋮
x ≡ ak (mod mk)
Here, m1, m2, … mk are pairwise coprime, which means that the greatest common divisor (GCD) of any pair mi and mj (for i!=j) is 1.
Objective
Find an integer x that satisfies all these congruences simultaneously.
Step-by-Step Solution
Step 1: Compute the product of all moduli.
Let M=m1 x m2 x … x mk
Step 2: Calculate individual terms.
For each i from 1 to k:
Compute Mi=M/mi.
Find the multiplicative inverse Ni of Mi modulo mi. This Ni satisfies the congruence:
Mi×Ni ≡ 1 (mod mi)
Step 3: Construct the solution.
The solution x is given by:
$$x = \sum_{i=1}^{k} a_i \times M_i \times N_i$$This sum will give you the unique solution modulo M, meaning x will satisfy all the given congruences.
Example
Suppose you have the following system of congruences:
x≡2 (mod 3)
x≡3 (mod 5)
x≡2 (mod 7)
Step 1: M = 3×5×7 = 105
Step 2: Compute
M1 = 105/3 = 35
M2 = 105/5 = 21
M3 = 105/7 = 15
Find the inverses:
N1 is the inverse of 35 modulo 3: 35×2≡1 (mod 3), so N1=2.
How did we solve for N1?
To solve the congruence 35 × N1 ≡ 1 ( mod 3 ), we’re looking for an integer N1 such that when 35×N1 is divided by 3, the remainder is 1.
Simplify the congruence: First, reduce 35 modulo 3:
35 ≡ 2 (mod 3)
This is because 35//3=11 with a remainder of 2.
So, the congruence simplifies to: 2×N1 ≡ 1 (mod 3)
Solve for N1: Now, find an integer N1 such that:
2×N1 ≡ 1 (mod3)
To do this, try values of N1 modulo 3:
If N1=1, then 2×1=2≡2(mod3) . Notice the value is not 1; but we want 1.
If N1=2, then 2×2=4≡1(mod3)
So, N1=2 is the solution.
Thus, N1=2 satisfies the congruence 35×N1≡1(mod3).
Similarly, find the exact values for N2 and N3.
N2 is the inverse of 21 modulo 5: 21×1≡1 (mod 5), so N2=1.
N3 is the inverse of 15 modulo 7: 15×1≡1 (mod 7), so N3=1.
Step 3: Calculate x:
x= ((2×35×2) + (3×21×1) + (2×15×1)) (mod 105)
x = (140+63+30) (mod 105) = 233 (mod 105) = 23
So, the solution is x≡23 (mod 105).
Interpretation
This means that 23 is the unique solution modulo 105 that satisfies all the original congruences.
Proof
Statement of the Theorem:
Suppose we have a system of congruences:
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
$$ \vdots \notag $$x ≡ ak (mod mk)
where the moduli m1,m2,…,mk are pairwise coprime (i.e., gcd(mi,mj)=1 for all i ≠ j).
The Chinese Remainder Theorem tells us that there exists a unique solution x modulo M, where M=m1×m2×⋯×mk.
Let’s break down the proof into simple steps.
Constructing a Solution:
First, define the total modulus M as:
M=m1 x m2 x…x mk
For each i, define: Mi = M / mi
Since Mi is the product of all moduli except mi, it is clear that Mi is divisible by all mj for j≠i, meaning Mi ≡ 0 (mod mj) for j≠i.
Finding Inverses:
Next, for each i, we find an integer yi such that:
yi×Mi ≡ 1 (mod mi)
This yi exists because Mi and mi are coprime. (This is guaranteed by the fact that the moduli m1,m2,…,mk are pairwise coprime.)
Constructing x:
Now, we construct the solution x as:
$$x = \sum_{i=1}^{k} a_i \times y_i \times M_i $$We need to verify that this xx satisfies all the congruences.
Verification:
Consider x modulo mj for any j:
$$ x \equiv \sum_{i=1}^{k} a_i \times y_i \times M_i \quad ( mod \quad m_j) $$Since Mi≡0 (mod mj) for all i≠j, only the term where i=j remains:
x≡aj * yj * Mj (mod mj)
By the choice of yj, we have yj×Mj≡1 (mod mj), so:
x ≡ aj (mod mj)
Thus, x satisfies all the original congruences.
Uniqueness:
The solution x is unique modulo M because if there were another solution x′, then x−x′ would be divisible by all mi, meaning x≡x′ (mod M).
Program
# Function to find gcd and the coefficients of Bézout's identity using the extended Euclidean algorithm
def extended_gcd(a, b):
print(f"The start of the function a = {a} and b = {b}")
# Initial values
old_r, r = a, b # r represents the remainder
old_x, x = 1, 0 # Coefficients for a
old_y, y = 0, 1 # Coefficients for b
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r # the same as in the Eucildean algorithm
old_x, x = x, old_x - quotient * x
# x: This represents the current coefficient for a in the linear combination.
# old_x: This represents the previous coefficient for a from the last iteration.
old_y, y = y, old_y - quotient * y
# old_r is the GCD, and old_x and old_y are the coefficients
return old_r, old_x, old_y
# Function to implement the Chinese Remainder Theorem
def chinese_remainder_theorem(a, m):
# Step 1: Compute the product of all moduli
M = 1
for mi in m:
M *= mi
# Step 2: Initialize result variable
x = 0
# Step 3: Compute each term and add it to the result
for i in range(len(a)):
Mi = M // m[i] # Compute Mi = M / mi
# Find the multiplicative inverse of Mi mod mi
gcd, inverse, _ = extended_gcd(Mi, m[i])
# Ensure that gcd is 1 (they are coprime)
if gcd != 1:
raise ValueError(f"The moduli {m} are not pairwise coprime.")
# Add the current term to the result
x += a[i] * inverse * Mi
# Step 4: Return the result mod M (smallest non-negative solution)
return x % M
# Example usage
a = [2, 3, 1]
m = [3, 5, 7]
result = chinese_remainder_theorem(a, m)
print(f"The solution x is: {result}")
Product Calculation: The product M of all the moduli is computed using a simple loop.
Result Calculation: We loop through each congruence to calculate the contribution of each term and sum them up.
Modulus Calculation: The final result is taken modulo M to ensure it’s the smallest non-negative solution.
Computational Complexity
The computational complexity of the program can be analyzed by breaking down the main steps:
Product Calculation (M):
Calculating the product of all moduli m requires iterating through the list m, which has a time complexity of O(n)O(n), where nn is the number of congruences (or moduli).
Extended Euclidean Algorithm (extended_gcd): The Extended Euclidean Algorithm, which is used to find the multiplicative inverse, runs in O(log(min(a,b))). Since this function is called for each modulus, the overall time complexity for this part is O(n log mmax), where mmax is the largest modulus.
Final Result Calculation:
The final result is computed by summing up the contributions from each modulus, which involves n multiplications and additions. This also takes O(n) time.
Overall Complexity:
Multiplicative Inverses: The most computationally expensive part is computing the multiplicative inverses using the Extended Euclidean Algorithm. This step dominates the overall complexity. Final Complexity: Combining all these, the overall time complexity of the program is O(n log mmax), where n is the number of moduli (congruences), and mmax is the largest modulus.
This means that as the number of moduli increases, or as the size of the moduli increases, the time taken by the program increases proportionally to the number of moduli and logarithmically with respect to the size of the moduli.
