Find the number x, that satisfies all the n equations simultaneously: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:
- x = r1 (mod p1)
- x = r2 (mod p2)
- x = rk (mod pk)
- x = rn (mod 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).