Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a mathematical theorem that states that if we have a system of linear congruences (equations of the form "x ≡ a mod m") with pairwise coprime moduli, then there exists a unique solution for x modulo the product of the moduli.

The theorem is called "Chinese" because it was first stated by the ancient Chinese mathematician Sun Tzu Suan Ching.

The CRT is particularly useful in solving systems of simultaneous modular equations that are difficult or impossible to solve individually. For example, if we have two congruences:

$$x \equiv 3 \bmod 4 \\ x \equiv 2 \bmod 5$$

It is not possible to find a single solution for x that satisfies both congruences.

However, using the CRT, we can find a unique solution for x that satisfies both congruences modulo the product of the moduli (20).

The CRT has many applications in cryptography, number theory, and computer science. For example, it is used in RSA encryption to speed up the calculation of the modular inverse, and in constructing public-key cryptosystems based on integer factorization.

Algorithm

In order to calculate a solution, two variables are needed :

$$N = n_1 \cdot n_2 \cdot n_3 \cdot ... \cdot n_i \\\text{}\\ E_i = \left[ \frac{N}{n_1}, \frac{N}{n_2}, \frac{N}{n_3},...,\frac{N}{n_i}\right]$$

The Ei values are composed multiplying all the n_values each others except n at position i.

For each elements of E , the inverse (mod ni) y can be calculated using the Fermat's Little theorem :

$$E_i \cdot y_i = 1 \bmod n_i$$

Then a solution for x can be calculated using the following equation :

$$x = a_1 \cdot E_1 \cdot y_1 + a_2 \cdot E_2 \cdot y_2 + a_3 \cdot E_3 \cdot y_3 + ... + a_i \cdot E_i \cdot y_i$$

The unique solution is then x % N

Python

# remind, x = a mod n
# All the a values
a = [2,4,8]
# All the n values
n = [4,5,17]

N = 1

# Calcul N value
for i in n:
    N = N * i

# Compute E
E = [N // n[i] for i in range(len(n))]

# Get all y values
y = [pow(E[i],n[i]-2,n[i]) for i in range(len(n))]

# do the calcul x = ai * Ni * yi ... 
x = 0
for i in range(len(n)):
        x += a[i]*E[i]*y[i]
# Get the uniq solution
x %= N
print(x)

Resources

Chinese remainder theoremWikipedia