# Chinese Remainder Theorem synthesis algorithm

Suppose m = pq where p and q are large, distinct primes. In the previous post we said that calculations mod m can often be carried out more efficiently by working mod p and mod q, then combining the results to get back to a result mod m.

The Chinese Remainder Theorem assures us that the system of congruences

has a unique solution mod m, but the theorem doesn’t say how to compute x efficiently.

H. L. Garner developed an algorithm to directly compute x [1]:

You compute the inverse of q mod p once and save it, then solving the system above for multiple values of a and b is very efficient.

Garner’s algorithm extends to more than two factors. We will present the general case of his algorithm below, but first we do a concrete example with RSA keys.

## RSA key example

This is a continuation of the example at the bottom of this post.

This shows that the numbers in the key file besides those that are strictly necessary for the RSA algorithm are numbers needed for Garner’s algorithm.

What the key file calls “coefficient” is the inverse of q modulo p.

What the key file calls “exponent1” is the the decryption exponent d reduced mod p-1. Similarly, “exponent2” is d reduced mod q-1 as explained here.

    from sympy import lcm

prime1 = 0xf33514...d9
prime2 = 0xfee496...51

publicExponent = 65537
privateExponent = 0x03896d...91

coefficient = 0x4d5a4c...b7 # q^-1 mod p
assert(coefficient*prime2 % prime1 == 1)

exponent1 = 0x37cc69...a1 # e % phi(p)
exponent2 = 0x2aa06f...01 # e % phi(q)
assert(privateExponent % (prime1 - 1) == exponent1)
assert(privateExponent % (prime2 - 1) == exponent2)


## More factors

Garner’s algorithm can be used more generally when m is the product of more than two primes [2]. Suppose

where the mi are pairwise relatively prime (not necessarily prime). Then the system of congruences

for i = 1, 2, 3, …, n can be solved by looking for a solution of the form

where

Again, in practice the modular inverses of the products of the ms would be precomputed and cached.

## Related posts

[1] Ferguson, Schneier, Kohno. Cryptography Engineering. Wiley. 2010.

[2] Geddes, Czapor, and Labahn. Algorithms for Computer Algebra. Kluwer Academic Publishers. 1992.