Chinese Remainder Theorem

Introduction

The Chinese Remainder Theorem (CRT) is a fundamental concept in number theory that provides a way to solve systems of linear congruences. Dating back to ancient Chinese mathematics from the 3rd century CE, this theorem allows us to find a unique solution to a system of congruences with coprime moduli.

In programming, the CRT finds applications in various domains including:

• Cryptography algorithms (like RSA)
• Hashing functions
• Distributed computing
• Error correction codes
• Efficient computation with large numbers

In this tutorial, we'll break down the theorem, understand its mathematical foundation, and see how to implement it in code.

Mathematical Foundation

Congruence Notation

Before diving into the theorem, let's quickly review congruence notation:

We say "a is congruent to b modulo m" and write:

a ≡ b (mod m)

This means that a and b have the same remainder when divided by m, or equivalently, m divides the difference (a-b).

Statement of the Chinese Remainder Theorem

Given a system of congruences:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₙ (mod mₙ)

If the moduli m₁, m₂, ..., mₙ are pairwise coprime (meaning any two different moduli share no common factor except 1), then there exists a unique solution x modulo M = m₁ × m₂ × ... × mₙ.

Algorithm for Solving CRT

Here's a step-by-step approach to find the solution:

1. Calculate M = m₁ × m₂ × ... × mₙ
2. For each i, calculate Mᵢ = M / mᵢ
3. For each i, find M'ᵢ such that M'ᵢ × Mᵢ ≡ 1 (mod mᵢ) (this is the modular multiplicative inverse)
4. The solution is: x = (a₁ × M₁ × M'₁ + a₂ × M₂ × M'₂ + ... + aₙ × Mₙ × M'ₙ) mod M

Let's implement this algorithm in code.

Implementation in Code

Finding Modular Multiplicative Inverse

First, we need a function to find the modular multiplicative inverse using the extended Euclidean algorithm:

python

def mod_inverse(a, m):
    """
    Returns the modular multiplicative inverse of a under modulo m.
    """
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def extended_gcd(a, b):
    """
    Extended Euclidean Algorithm to find gcd(a, b) and coefficients x, y
    where ax + by = gcd(a, b)
    """
    if a == 0:
        return b, 0, 1
    else:
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y

Implementing the Chinese Remainder Theorem

Now, let's implement the CRT algorithm:

python

def chinese_remainder_theorem(remainders, moduli):
    """
    Solve the system of congruences using Chinese Remainder Theorem.
    
    Args:
        remainders: List of remainders [a₁, a₂, ..., aₙ]
        moduli: List of moduli [m₁, m₂, ..., mₙ]
        
    Returns:
        The solution x such that x ≡ aᵢ (mod mᵢ) for all i.
    """
    # Check if moduli are pairwise coprime
    for i in range(len(moduli)):
        for j in range(i + 1, len(moduli)):
            if gcd(moduli[i], moduli[j]) != 1:
                raise ValueError("Moduli must be pairwise coprime")
                
    # Calculate M = m₁ × m₂ × ... × mₙ
    M = 1
    for m in moduli:
        M *= m
        
    # Calculate Mᵢ = M / mᵢ and M'ᵢ
    result = 0
    for i in range(len(remainders)):
        Mi = M // moduli[i]
        Mi_inv = mod_inverse(Mi, moduli[i])
        result += remainders[i] * Mi * Mi_inv
        
    return result % M

def gcd(a, b):
    """
    Calculate the greatest common divisor of a and b.
    """
    while b:
        a, b = b, a % b
    return a

Example Usage

Let's work through an example to understand how the Chinese Remainder Theorem works in practice:

Suppose we have the following system of congruences:

• x ≡ 2 (mod 3)
• x ≡ 3 (mod 5)
• x ≡ 2 (mod 7)

We want to find the value of x.

python

remainders = [2, 3, 2]
moduli = [3, 5, 7]
solution = chinese_remainder_theorem(remainders, moduli)
print(f"Solution: x = {solution}")

Output:

Solution: x = 23

Let's verify that this solution works:

• 23 mod 3 = 2 ✓
• 23 mod 5 = 3 ✓
• 23 mod 7 = 2 ✓

This confirms that x = 23 satisfies all three congruences.

Step-by-Step Explanation of the Example

Let's break down the calculation steps:

1. M = 3 × 5 × 7 = 105
2. M₁ = M / 3 = 35, M₂ = M / 5 = 21, M₃ = M / 7 = 15
3. Find modular multiplicative inverses:
   • M'₁ = 2 because 35 × 2 ≡ 1 (mod 3)
   • M'₂ = 1 because 21 × 1 ≡ 1 (mod 5)
   • M'₃ = 1 because 15 × 1 ≡ 1 (mod 7)
4. Calculate the solution:
   • x = (2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1) mod 105
   • x = (140 + 63 + 30) mod 105
   • x = 233 mod 105
   • x = 23

Real-World Applications

1. Cryptography - RSA Algorithm

The RSA algorithm uses the Chinese Remainder Theorem to speed up decryption:

python

def rsa_decryption_with_crt(c, p, q, d):
    """
    RSA decryption using CRT for speedup.
    
    Args:
        c: ciphertext
        p, q: prime factors of n
        d: private exponent
        
    Returns:
        Decrypted message
    """
    dp = d % (p - 1)
    dq = d % (q - 1)
    
    m1 = pow(c, dp, p)
    m2 = pow(c, dq, q)
    
    # Calculate qinv = q^(-1) mod p
    qinv = mod_inverse(q, p)
    
    h = (qinv * (m1 - m2)) % p
    
    # CRT formula: m = m2 + h * q
    m = m2 + h * q
    
    return m

2. Scheduling Problems

Suppose you need to find time slots that satisfy multiple periodic constraints:

python

def find_meeting_time(periods, offsets):
    """
    Find a time slot that satisfies multiple periodic constraints.
    
    Args:
        periods: List of periods [p₁, p₂, ..., pₙ]
        offsets: List of offsets [o₁, o₂, ..., oₙ]
    
    Returns:
        The earliest time slot that satisfies all constraints
    """
    # Convert to CRT form:
    # Find x such that x ≡ o₁ (mod p₁), x ≡ o₂ (mod p₂), etc.
    return chinese_remainder_theorem(offsets, periods)

# Example: Find a meeting time where:
# - Person A is available every 4 hours, starting at hour 1
# - Person B is available every 3 hours, starting at hour 2
# - Person C is available every 5 hours, starting at hour 4

periods = [4, 3, 5]
offsets = [1, 2, 4]

meeting_time = find_meeting_time(periods, offsets)
print(f"The earliest meeting time is at hour {meeting_time}")

Output:

The earliest meeting time is at hour 49

3. Hash Function Design

CRT can be used to design hash functions with controlled collision behavior:

python

def crt_hash(data, moduli):
    """
    A simple hash function using CRT principles.
    
    Args:
        data: Input data (list of integers)
        moduli: List of prime moduli
    
    Returns:
        A hash value
    """
    remainders = [sum(data) % m for m in moduli]
    return chinese_remainder_theorem(remainders, moduli)

# Example
moduli = [17, 19, 23]  # Small primes for demonstration
data1 = [5, 10, 15, 20]
data2 = [7, 14, 21, 28]

print(f"Hash of data1: {crt_hash(data1, moduli)}")
print(f"Hash of data2: {crt_hash(data2, moduli)}")

Algorithm Complexity

• Time Complexity: O(n²), where n is the number of congruences. The most computationally expensive part is finding the modular multiplicative inverses.
• Space Complexity: O(n), as we need to store the remainders, moduli, and intermediate calculations.

Potential Pitfalls and Limitations

1. Non-coprime moduli: The standard CRT requires the moduli to be pairwise coprime. If they're not, you need to use a more general form of the theorem.

2. Large numbers: When working with very large moduli, you might encounter overflow issues. Consider using a language or library that supports arbitrary-precision arithmetic.

3. Numerical stability: The straightforward implementation can lead to large intermediate results, which may cause numerical issues.

Summary

The Chinese Remainder Theorem is a powerful technique in number theory that allows us to solve systems of congruences efficiently. In this tutorial, we've explored:

1. The mathematical foundation of the CRT
2. A step-by-step algorithm for implementing the theorem
3. Practical code examples in Python
4. Real-world applications in cryptography, scheduling, and hash function design

The CRT exemplifies how ancient mathematics continues to find applications in modern computing, especially in scenarios involving modular arithmetic and large number computations.

Exercises

1. Implement a function that solves CRT when the moduli aren't pairwise coprime.
2. Solve this system of congruences using your implementation:
   • x ≡ 4 (mod 5)
   • x ≡ 7 (mod 11)
   • x ≡ 8 (mod 13)
3. Extend the chinese_remainder_theorem() function to handle negative remainders.
4. Research and implement a variant of CRT that works with simultaneous linear congruences (e.g., ax ≡ b (mod m)).
5. Use the CRT to implement a simplified version of the RSA algorithm.

Additional Resources

• "Elementary Number Theory" by David M. Burton
• "A Course in Number Theory and Cryptography" by Neal Koblitz
• "Concrete Mathematics" by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik
• Online course: "Number Theory for Cryptography" on Coursera

Remember that mastering the Chinese Remainder Theorem opens the door to understanding many advanced algorithms in cryptography and computer science. Practice with different examples to solidify your understanding!