Cryptography: Theory and Practice:The RSA System and Factoring | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

4.2.2 The Chinese Remainder Theorem

The Chinese remainder theorem is really a method of solving certain systems of congruences. Suppose m₁, . . . , m_r are pairwise relatively prime positive integers (that is, gcd (m_i, m_j) = 1 if i ≠ j). Suppose a₁, . . ., a_r are integers, and consider the following system of congruences:

The Chinese remainder theorem asserts that this system has a unique solution modulo M = m₁ × m₂ × . . . × m_r. We will prove this result in this section, and also describe an efficient algorithm for solving systems of congruences of this type.

It is convenient to study the function , which we define as follows:

Example 4.2

Suppose r = 2, m₁ = 5 and m₂ = 3, so M = 15. Then the function π has the following values:

Proving the Chinese remainder theorem amounts to proving that this function π we have defined is a bijection. In Example 4.2 this is easily seen to be the case. In fact, we will be able to give an explicit general formula for the inverse function π^-1.

For 1 ≤ i ≤ r, define

Then it is not difficult to see that

for 1 ≤ i ≤ r. Next, for 1 ≤ i ≤ r, define

(This inverse exists since gcd(M_i, m_i) = 1, and it can be found using the Euclidean algorithm.) Note that

for i ≤ i ≤ r.

Now, define a function follows:

We will show that the function ρ = π^-1, i.e., it provides an explicit formula for solving the original system of congruences.

Denote X = ρ(a₁, . . ., a_r), and let 1 ≤ j ≤ r. Consider a term a_iM_iy_i in the above summation, reduced modulo m_j: If i = j, then

since

On the other hand, if i ≠ j, then

since m_j | M_i in this case. Thus, we have that

Since this is true for all j, 1 ≤ j ≤ r, X is a solution to the system of congruences.

At this point, we need to show that the solution X is unique modulo M. But this can be done by simple counting. The function π is a function from a domain of cardinality M to a range of cardinality M. We have just proved that π is a surjective (i.e., onto) function. Hence, π must also be injective (i.e., one-to-one), since the domain and range have the same cardinality. It follows that π is a bijection and π^-1 = ρ. Note also that π^-1 is a linear function of its arguments a₁, . . . , a_r.

Here is a bigger example to illustrate.

Example 4.3

Suppose r = 3, m₁ = 7, m₂ = 11 and m₃ = 13. Then M = 1001. We compute M₁ = 143, M₂ = 91 and M₃ = 77, and then y₁ = 5, y₂ = 4 and y₃ = 12. Then the function is the following:

For example, if x ≡ 5 (mod 7), x ≡ 3 (mod 11) and x ≡ 10 (mod 13), then this formula tells us that

This can be verified by reducing 894 modulo 7, 11 and 13.

For future reference, we record the results of this section as a theorem.

THEOREM 4.3 (Chinese Remainder Theorem)

Suppose m₁, . . ., m_r are pairwise relatively prime positive integers, and suppose a₁, . . ., a_r are integers. Then, the system of r congruences x ≡ a_i (mod m_i) (1 ≤ i ≤ r) has a unique solution modulo M = m₁ × . . . × m_r, which is given by

where M_i = M/m_i and y_i = M_i^-1 mod m_i, for 1 ≤ i ≤ r.

Table of Contents