# Chinese Remainder Theorem

Cryptography Math

## Basic

If moduli (`n1`, `n2`, etc.) are co-primes, the following rules hold:

``````x ≡ a1 mod n1 # means `x % n1 = a1`
x ≡ a2 mod n2 # means `x % n2 = a2`
...
x ≡ ak mod nk # means `x % nk = ak`
``````

In addition, if the values of `a1`, `a2`, … `ak` and `n1`, `n2`, … `nk` are defined, we can calculate `x` by the following approach.

``````# Calculate N
N = n1 * n2 * n3 * ... * nk

# Calculate Ni (N1, N2, ..., Nk)
N1 = n2 * n3 * n4 ... * nk
N2 = n1 * n3 * n4 ... * nk
N3 = n1 * n2 * n4 ... * nk
...
Nk = n1 * n2 * n3 ... * n(k-1)

# Calculate xi (x1, x2, ..., xk)
N1*x1 ≡ 1 (mod n1) # means `N1*x1 % n1 = 1`
N2*x2 ≡ 1 (mod n2) # means `N2*x2 % n2 = 1`
N3*x3 ≡ 1 (mod n3) # means `N3*x3 % n3 = 1`
...
Nk*xk ≡ 1 (mod nk) # means `Nk*xk % nk = 1`

# x is sum of each ai*Ni*xi (mod N)
x = a1*N1*x1 + a2*N2*x2 + a3*N3*x3 + ... + ak*Nk*xk (mod N)
``````

## Using crt method in Sympy

``````from sympy.ntheory.modular import crt

m = [7, 15]
a = [5, 12]
(x, y) = crt(m, a)
# x = 68, y = 77
``````