Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
The Chinese remainder theorem is really a method of solving certain systems of congruences. Suppose m1, . . . , mr are pairwise relatively prime positive integers (that is, gcd (mi, mj) = 1 if i ≠ j). Suppose a1, . . ., ar are integers, and consider the following system of congruences:
The Chinese remainder theorem asserts that this system has a unique solution modulo M = m1 × m2 × . . . × mr. 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, m1 = 5 and m2 = 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(Mi, mi) = 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 = ρ(a1, . . ., ar), and let 1 ≤ j ≤ r. Consider a term aiMiyi in the above summation, reduced modulo mj: If i = j, then
since
On the other hand, if i ≠ j, then
since mj | Mi 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 a1, . . . , ar.
Here is a bigger example to illustrate.
Example 4.3
Suppose r = 3, m1 = 7, m2 = 11 and m3 = 13. Then M = 1001. We compute M1 = 143, M2 = 91 and M3 = 77, and then y1 = 5, y2 = 4 and y3 = 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 m1, . . ., mr are pairwise relatively prime positive integers, and suppose a1, . . ., ar are integers. Then, the system of r congruences x ≡ ai (mod mi) (1 ≤ i ≤ r) has a unique solution modulo M = m1 × . . . × mr, which is given by
where Mi = M/mi and yi = Mi-1 mod mi, for 1 ≤ i ≤ r.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC