Suppose *m* is a large integer that you are able to factor. To keep things simple, suppose *m* = *pq* where *p* and *q* are distinct primes; everything in this post generalizes easily to the case of *m* having more than two factors.

You can carry out calculations mod *m* more efficiently by carrying out the same calculations mod *p* and mod *q*, then combining the results. We **analyze** *m* into its remainders by *p* and *q*, carry out our calculations, then **synthesize** the results to get back to a result mod *m*.

The Chinese Remainder Theorem (CRT) says that this synthesis is possible; Garner’s algorithm, the subject of the next post, shows how to compute the result promised by the CRT.

For example, if we want to multiply *xy* mod *m*, we can analyze *x* and *y* as follows.

Then

and by repeatedly multiplying *x* by itself we have

Now suppose *p* and *q* are 1024-bit primes, as they might be in an implementation of RSA encryption. We can carry out exponentiation mod *p* and mod *q*, using 1024-bit numbers, rather than working mod *n* with 2048-bit numbers.

Furthermore, we can apply Euler’s theorem (or the special case Fermat’s little theorem) to reduce the size of the exponents.

Assuming again that *p* and *q* are 1024-bit numbers, and assuming *e* is a 2048-bit number, by working mod *p* and mod *q* we can use exponents that are 1024-bit numbers.

We still have to put our pieces back together to get the value of *x*^{e} mod *n*, but that’s the subject of the next post.

The trick of working modulo factors is used to speed up RSA decryption. It cannot be used for encryption since *p* and *q* are secret.

The next post shows that is in fact used in implementing RSA, and that a key file contains the decryption exponent reduced mod *p*-1 and mod *q*-1.