Computing the Chinese Remainder Theorem - Eli Bendersky's website

A practical look at CRT solvers

In a previous post, we covered the mathematical foundations of the Chinese Remainder Theorem (CRT). Here, we shift focus to the practical side: implementing solvers for systems of congruences. Recall that when the moduli ni are pairwise co-prime, a system of congruences has a unique solution modulo the product N of all moduli.

Brute force: unreasonable approach

The most straightforward solver is exhaustive search. Given a small system, you can simply iterate from 1 to N-1, checking each candidate against every congruence. For example, the system:

x ≡ 0 (mod 3),
x ≡ 3 (mod 4),
x ≡ 4 (mod 5)

yields a unique solution modulo 60 (39 in this case, with further solutions found by adding 60).

This naive approach is easy to code and works for tiny inputs, but it scales terribly. Its time complexity is O(N * k), where k is the number of congruences. In number-theoretic terms, since N grows exponentially with its bit size, the algorithm is exponential. For a system where N is a 19-digit number, brute-force search is simply not viable; a smarter method is required.

Sieve-based search: better, still exponential

A more practical improvement builds the solution incrementally. The key insight is that the CRT guarantees a unique solution for *any* subset of the congruences. So, you can start with the first congruence and extend the solution one congruence at a time.

Based on a solution x for the first j congruences (which is unique modulo the product of the first j moduli), the solution for the next congruence lies within the arithmetic progression x + k * (product of first j moduli). You search for the first k that satisfies the next congruence, and you have a solution for the first j+1 congruences. Repeat until all are satisfied.

For efficiency, sort the congruences by decreasing moduli, handling the largest constraints first. On a moderately large example where brute force would run essentially forever, this approach completes in under a millisecond. However, this method is still exponential in the bit size of the numbers; for cryptographic-scale inputs, we need a fundamentally better algorithm.

Constructive method: doing it right

The theorem's proof itself provides an efficient construction. Given congruences with moduli ni, the solution is:

x = Σ ai * Mi * mi' (mod N)

where Mi = N / ni and mi' is the multiplicative inverse of Mi modulo ni. Modular inverses are computed efficiently via the extended Euclidean algorithm.

In Go, the math/big package makes this straightforward. Unlike the integer-limited version of the sieve, using big.Int throughout allows the solver to handle arbitrarily large numbers. This constructive algorithm runs in O(n²) time, and benchmarks show it is roughly 20x faster than an equally capable sieve-based implementation on a 144-bit problem.

The full code, including tests and benchmarks, is available in the accompanying repository.

Note: While both the naive and sieve-based methods are valid
for small problems, any serious CRT solver should use the constructive approach
to handle the large numbers that often appear in practice.