# 3: Chinese Remainder Theorem

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 xr u, as desired. By a symmetric argument, we can see that xs ?, 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 xr x’ and xs x’, it must be that xx’ is a multiple of r and a multiple of s. Since r and s are relatively prime, their least common multiple is rs, so xx’ must be a multiple of rs. Hence, xrs 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 xr u and xs ?. The CRT says that the 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:

1. 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.
2. 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.
3. 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 × ℤs-names” of two items, we can add them (first components mod 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 ∈ ℤpq. Since 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 n3 steps. Let’s suppose that p and q are each n bits long, so that the RSA modulus N is 2n bits long. Performing ccd modulo N therefore costs about (2n)3 = 8n3 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 n3 + n3 = 2n3. 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.

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

4Fun fact: this yields an alternative proof that ϕ(pq) = (p − 1)(q − 1) when p and q are prime. That is, ϕ(pq) = |Zpq| = |Zp × Zq| = (p − 1)(q − 1).