# 3: Chinese Remainder Theorem

- Page ID
- 7399

The multiplicative group ℤ^{∗}_{N} has some interesting structure when *N* is the product of distinct primes. We can use this structure to optimize some algorithms related to RSA.

**History.** Some time around the 4th century CE, Chinese mathematician Sun Tzu Suan Ching discussed problems relating to simultaneous equations of modular arithmetic:

*We have a number of things, but we do not know exactly how many. If we count them by threes we have two left over. If we count them by fives we have three left over. If we count them by sevens we have two left over. How many things are there? ^{3}*

In our notation, he is asking for a solution *x* to the following system of equations:

A generalized way to solve equations of this kind was later given by mathematician Qin Jiushao in 1247 CE. For our eventual application to RSA, we will only need to consider the case of two simultaneous equations.

**Theorem 13.3: CRT**

Suppose gcd(*r,s*) = 1. Then for all integers *u*,?, there is a solution for *x* in the following system of equations:

Furthermore, this solution is *unique* modulo *rs*.

**Proof**

Since gcd(*r,s*) = 1, we have by Bezout’s theorem that 1 = *ar* + *bs* for some integers *a* and *b*. Furthermore, *b* and *s* are multiplicative inverses modulo *r*. Now choose *x* = ?*ar* + *ubs*. Then,

So *x* ≡_{r}*u*, as desired. By a symmetric argument, we can see that *x* ≡* _{s}* ?, so

*x*is a solution to the system of equations.

Now we argue why the solution is *unique* modulo *rs*. Suppose *x* and *x’*are two solutions to the system of equations, so we have:

Since *x* ≡_{r}*x’* and *x* ≡_{s}*x’*, it must be that *x* − *x’* is a multiple of *r* and a multiple of *s*. Since *r* and *s* are relatively prime, their least common multiple is *rs*, so *x* − *x’* must be a multiple of *rs*. Hence, *x* ≡_{rs}*x’*. So any two solutions to this system of equations are congruent mod *rs*.

We can associate every pair (*u*,?) ∈ ℤ_{r} × ℤ_{s} with its corresponding system of equations of the above form (with *u* and ? as the right hand-sides). The CRT suggests a relationship between these pairs (*u*,?) ∈ ℤ_{r} × ℤ_{s} and elements of ℤ_{rs}.

For *x* ∈ ℤ* _{rs}*, and (

*u*,?) ∈ ℤ

_{r}× ℤ

_{s}, let us write

to mean that *x* is a solution to *x* ≡* _{r} u* and

*x*≡

*?. The CRT says that the*

_{s}^{crt}←→ relation is a

*bijection*(1-to-1 correspondence) between elements of ℤ

_{rs}and elements of ℤ

_{r}× ℤ

_{s}.

In fact, the relationship is even deeper than that. Consider the following observations:

- If
*x*^{crt}←→ (*u*,?) and*x’*^{crt}←→ (*u’*,?’), then*x*+*x’*^{crt}←→ (*u*+*u’*, ? + ?’). You can see this by adding relevant equations together from the system of equations. Note here that the addition*x*+*x’*is done mod*rs*; the addition*u*+*u’*is done mod*r*; and the addition ? + ?’ is done mod*s*. - If
*x*^{crt}←→ (*u*,?) and*x’*^{crt}←→ (*u’*, ?’), then*xx’*^{crt}←→ (*uu’*,??’). You can see this by multiplying relevant equations together from the system of equations. As above, the multiplication*xx’*is mod*rs*;*uu’*is done mod*r*; ??’ is done mod*s*. - Suppose
*x*^{crt}←→ (*u*,?). Then gcd(*x,rs*) = 1 if and only if gcd(*u,r*) = gcd(?,*s*) = 1. In other words, the^{crt}←→ relation is a 1-to-1 correspondence between elements of ℤ ∗*rs*and elements of ℤ ∗*r*× ℤ ∗*s*.^{4}

The bottom line is that the CRT demonstrates that ℤ_{rs} and ℤ_{r} × ℤ_{s}**are essentially the same mathematical object**. In the terminology of abstract algebra, the two structures are *isomorphic*.

Think of ℤ_{rs} and ℤ* _{r}* × ℤ

_{s}being two different kinds of

*names*or

*encodings*for the same set of items. If we know the “ℤ

_{rs}-names” of two items, we can add them (mod

*rs*) to get the ℤ

_{rs}-name of the result. If we know the “ℤ

*× ℤ*

_{r}*-names” of two items, we can add them (first components mod*

_{s}*r*and second components mod

*s*) to get the ℤ

_{r}× ℤ

_{s}-name of the result. The CRT says that both of these ways of adding give the same results.

Additionally, the proof of the CRT shows us how to convert between these styles of names for a given object. So given *x* ∈ ℤ* _{rs}*, we can compute (

*x % r,x % s*), which is the corresponding element/name in ℤ

*× ℤ*

_{r}_{s}. Given (

*u*,?) ∈ ℤ

_{r}× ℤ

_{s}, we can compute

*x*= ?

*ar*+

*ubs % rs*(where

*a*and

*b*are computed from the extended Euclidean algorithm) to obtain the corresponding element/name

*x*∈ ℤ

*.*

_{rs} From a **mathematical** perspective, ℤ_{rs} and ℤ_{r} × ℤ_{s} are the same object. However, from a **computational** perspective, there might be reason to favor one over the other. In fact, it turns out that doing computations in the ℤ_{r} × ℤ_{s} realm is significantly cheaper.

**Application to RSA**

In the context of RSA decryption, we are interested in taking *c* ∈ ℤ* _{pq}* and computing

*cd*∈ ℤ

*. Since*

_{pq}*p*and

*q*are distinct primes, gcd(

*p,q*) = 1 and the CRT is in effect.

Thinking in terms of ℤ* _{pq}*-arithmetic, raising

*c*to the

*d*power is rather straightforward. However, the CRT suggests that another approach is possible: We could convert

*c*into its ℤ

_{p}× ℤ

_{q}representation, do the exponentiation under that representation, and then convert back into the ℤ

_{pq}representation. This approach corresponds to the bold arrows in Figure 13.1, and the CRT guarantees that the result will be the same either way.

Now why would we ever want to compute things this way? Performing an exponentiation modulo an *n*-bit number requires about *n*^{3} steps. Let’s suppose that *p* and *q* are each *n* bits long, so that the RSA modulus *N* is 2*n* bits long. Performing *c* ↦ *c ^{d}* modulo

*N*therefore costs about (2

*n*)

^{3}= 8

*n*

^{3}total.

The CRT approach involves two modular exponentiations — one mod *p* and one mod *q*. Each of these moduli are only *n* bits long, so the total cost is *n*^{3} + *n*^{3} = 2*n*^{3}. **The CRT approach is 4 times faster!** Of course, we are neglecting the cost of converting between representations, but that cost is very small in comparison to the cost of exponentiation.

It’s worth pointing out that this speedup can only be done for the RSA *inverse* function. One must know *p* and *q* in order to exploit the Chinese Remainder Theorem, and only the party performing the RSA inverse function typically knows this.

^{3}Translation due to Joseph Needham, *Science and Civilisation in China, vol. 3: Mathematics and Sciences
of the Heavens and Earth*, 1959.

^{4}Fun fact: this yields an alternative proof that *ϕ*(*pq*) = (*p* − 1)(*q* − 1) when *p* and *q* are prime. That is, *ϕ*(*pq*) = |**Z**^{∗}_{pq}| = |**Z**^{∗}_{p} × **Z**^{∗}* _{q}*| = (

*p*− 1)(

*q*− 1).