Chinese Remainder Theorem

By Sudheer S

August 29, 2024

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 ≡ a₁ (mod m₁)

x ≡ a₂ (mod m₂)

⋮

x ≡ a_k (mod m_k)

Here, m₁, m₂, … m_k are pairwise coprime, which means that the greatest common divisor (GCD) of any pair m_i and m_j (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=m₁ x m₂ x … x m_k

Step 2: Calculate individual terms.

For each i from 1 to k:

Compute Mi=M/m_i.

Find the multiplicative inverse N_i of M_i modulo m_i. This N_i satisfies the congruence:

M_i×N_i ≡ 1 (mod m_i)

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

M₁ = 105/3 = 35

M₂ = 105/5 = 21

M₃ = 105/7 = 15

Find the inverses:

N₁ is the inverse of 35 modulo 3: 35×2≡1 (mod 3), so N₁=2.

How did we solve for N₁?

To solve the congruence 35 × N₁ ≡ 1 ( mod 3 ), we’re looking for an integer N₁ such that when 35×N₁ 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×N₁ ≡ 1 (mod 3)

Solve for N₁: Now, find an integer N₁ such that:

2×N₁ ≡ 1 (mod3)

To do this, try values of N₁ modulo 3:

If N₁=1, then 2×1=2≡2(mod3) . Notice the value is not 1; but we want 1.

If N₁=2, then 2×2=4≡1(mod3)

So, N₁=2 is the solution.

Thus, N₁=2 satisfies the congruence 35×N₁≡1(mod3).

Similarly, find the exact values for N₂ and N₃.

N₂ is the inverse of 21 modulo 5: 21×1≡1 (mod 5), so N₂=1.

N₃ is the inverse of 15 modulo 7: 15×1≡1 (mod 7), so N₃=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 ≡ a_k (mod m_k)

where the moduli m1,m2,…,m_k are pairwise coprime (i.e., gcd⁡(m_i,m_j)=1 for all i ≠ j).

The Chinese Remainder Theorem tells us that there exists a unique solution x modulo M, where M=m1×m2×⋯×m_k.

Let’s break down the proof into simple steps.

Constructing a Solution:

First, define the total modulus M as:

M=m₁ x m₂ x…x m_k

For each i, define: M_i = M / mi

Since M_i is the product of all moduli except m_i, it is clear that M_i is divisible by all m_j for j≠i, meaning M_i ≡ 0 (mod m_j) for j≠i.

Finding Inverses:

Next, for each i, we find an integer y_i such that:

y_i×M_i ≡ 1 (mod m_i)

This y_i exists because M_i and m_i are coprime. (This is guaranteed by the fact that the moduli m₁,m₂,…,m_k 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 m_j 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≡a_j * y_j * M_j (mod mj)

By the choice of y_j, we have y_j×M_j≡1 (mod m_j), so:

x ≡ a_j (mod m_j)

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 m_i, 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 ⁡m_max), 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⁡ m^max), where n is the number of moduli (congruences), and m_max 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.