The Chinese Remainder Theorem

The Chinese Remainder Theorem is using to solve systems of congruences with different moduli. This states that, for any $k ∈ N$ and coprime natural numbers $n_1, . . . n_k ∈ N$, as well as integers $a_1, . . . a_k ∈ Z$, the so-called simultaneous congruences (in below) have a solution, and all possible solutions of this congruence system are congruent modulo the product $N = n_1 ·. . .·n_k$.

$$x ≡ a_1 \mod n_1 \\ x ≡ a_2 \mod n_2 \\ · · · \\ x ≡ a_k \mod n_k$$

def crt(a, n):
    assert len(a) == len(n), "len(a) != len(n)"
    N = reduce((lambda x, y: x * y), n)
    x = 0
    for j in range(len(n)):
        N_j = N / n[j]
        s_j = xgcd(N_j, n[j])[1]
        x = (x + a[j] * s_j * N_j) % N
    return x

Sage example:

CRT_list([4,1,3,0], [7,3,5,11])

Complexity: $O((\log N)^2)$