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.