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.

begin{align*} x &equiv x_p pmod p \ x &equiv x_q pmod q \ y &equiv y_p pmod p \ y &equiv y_q pmod q \ end{align*}

Then

begin{align*} xy &equiv x_py_p pmod p \ xy &equiv x_qy_q pmod q \ end{align*}

and by repeatedly multiplying x by itself we have

begin{align*} x^e &equiv x_p^e pmod p \ x^e &equiv x_q^e pmod q \ end{align*}

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.

begin{align*} x^e &equiv x_p^e equiv x_p^{e bmod p-1}pmod p \ x^e &equiv x_q^e equiv x_q^{e bmod q-1}pmod q end{align*}

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 xe 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.

The post Gaining efficiency by working modulo factors first appeared on John D. Cook.

Previous Post
Next Post