## The Chinese Remainder Theorem

Last updated: August 7th, 1995

The Chinese Remainder Theorem (CRT) gives the answer to the problem:
Find the number x, that satisfies all the n equations simultaneously:

- x = r1 (mod p1)
- x = r2 (mod p2)
- ...
- x = rk (mod pk)
- ...
- x = rn (mod pn)

We will assume here (for practical purposes) that the moduli pk are primes.
Then there exists a unique solution x modulo p1*p2*...*pn. The solution can
be found with the following algorithm:
Let P=p1*p2*...*pn

Let the numbers T1...Tn be defined so that for each Tk (k=1...n)

(P/pk)*Tk=1 (mod pk)

that is, Tk is the inverse of P/pk (mod pk). The inverse of a (mod p) can be
found for example by calculating a^(p-2) (mod p). Note that
a*a^(p-2)=a^(p-1)=1 (mod p).

Then the solution is

x = (P/p1)*r1*T1 + (P/p2)*r2*T2 + ... + (P/pn)*rn*Tn (mod P)

The good thing is, that you can calculate the factors (P/pk)*Tk beforehand, and
then to get x for different rk, you only need to do simple multiplications and
additions (supposing that the primes pk remain the same).

When using the CRT in a number theoretic transform, the algorithm can be
implemented very efficiently using only single-precision arithmetic when rk < pk
for all k. Now calculate first P/pk and Tk for all k (note that this only needs
to be done once). Then calculate

yk = rk*Tk (mod pk)

for all k. Now the solution is

x = (P/p1)*y1 + (P/p2)*y2 + ... + (P/pn)*yn (mod P)

Note that multiplying a multiprecision number (P/pk) with a single-precision
number only requires single-precision arithmetic (supposing your hardware does
double-width multiplication).

Back to
number theoretic transforms.