Chinese remainder theorem

 

Chinese remainder theorem refers to a result about congruences in number theory and its generalizations in abstract algebra.

Theorem statement

The original form of the theorem, contained in a third-century AD book by Chinese mathematician Sun Tzu [1] and later republished in a 1247 book by Qin Jiushao, is a statement about simultaneous congruences (see modular arithmetic).

Suppose n₁, n₂, …, n_k are integers which are pairwise coprime. Then, for any given integers a₁,a₂, …, a_k, there exists an integer x solving the system of simultaneous congruences

Failed to parse (unknown function\begin): \begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align}

Furthermore, all solutions x to this system are congruent modulo the product N = n₁n₂…n_k.

Sometimes, the simultaneous congruences can be solved even if the n_i's are not pairwise coprime. A solution x exists if and only if:

All solutions x are then congruent modulo the least common multiple of the n_i.

Versions of the Chinese remainder theorem were also known to Brahmagupta, and appear in Fibonacci's Liber Abaci (1202).

A constructive algorithm to find the solution

This algorithm only treats the situations where the n_i's are coprime. The method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.

Suppose, as above, that a solution is needed to the system of congruences:

Again, to begin, the product N = n₁n₂...n_k is defined. Then a solution x can be found as follows.

For each i the integers n_i and N / n_i are coprime. Using the extended Euclidean algorithm we can therefore find integers r_i and s_i such that r_in_i + s_iN / n_i = 1. Then, choosing the label e_i = s_iN / n_i, the above expression becomes:

Consider e_i. The above equation guarantees that its remainder, when divided by n_i, must be 1. On the other hand, since it is formed as s_iN / n_i, the presence of N guarantees that it's evenly divisible by any n_j so long as j≠i.

Because of this, combined with the multiplication rules allowed in congruences, one solution to the system of simultaneous congruences is:

For example, consider the problem of finding an integer x such that

Using the extended Euclidean algorithm for 3 and 4×5 = 20, we find (−13) × 3 + 2 × 20 = 1, i.e. e₁ = 40. Using the Euclidean algorithm for 4 and 3×5 = 15, we get (−11) × 4 + 3 × 15 = 1. Hence, e₂ = 45. Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (−2) × 12 = 1, meaning e₃ = −24. A solution x is therefore 2 × 40 + 3 × 45 + 1 × (−24) = 191. All other solutions are congruent to 191 modulo 60, (3 × 4 × 5 = 60) which means that they are all congruent to 11 modulo 60.

NOTE: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of e₁, e₂, and e₃. These sets however will produce the same solution i.e. 11 modulo 60.

Statement for principal ideal domains

For a principal ideal domain R the Chinese remainder theorem takes the following form: If u₁, ..., u_k are elements of R which are pairwise coprime, and u denotes the product u₁...u_k, then the quotient ring R/uR and the product ring R/u₁R × ⋯ × R/u_kR are isomorphic via the isomorphism

such that

The inverse isomorphism can be constructed as follows. For each i, the elements u_i and u/u_i are coprime, and therefore there exist elements r and s in R with

Set e_i = s u/u_i. Then the inverse of f is the map

such that

Note that this statement is a straightforward generalization of the above theorem about integer congruences: the ring Z of integers is a principal ideal domain, the surjectivity of the map f shows that every system of congruences of the form

can be solved for x, and the injectivity of the map f shows that all the solutions x are congruent modulo u.

Statement for general rings

The general form of the Chinese remainder theorem, which implies all the statements given above, can be formulated for rings and (two-sided) ideals. If R is a ring and I₁, ..., I_k are two-sided ideals of R which are pairwise coprime (meaning that I_i + I_j = R whenever i ≠ j), then the product I of these ideals is equal to their intersection, and the quotient ring R/I is isomorphic to the product ring R/I₁ x R/I₂ x ... x R/I_k via the isomorphism

such that

Applications

In the RSA algorithm calculations are made modulo n, where n is a product of two primes p and q. Common sizes for n are 1024, 2048 or 4096 bits, making calculations very time-consuming. Using Chinese remaindering these calculations can be transported from the ring to the ring . The sum of the bit sizes of p and q is the bit size of n, making p and q considerably smaller than n. This greatly speeds up calculations. Note that RSA algorithm implementations using Chinese remaindering are more susceptible to fault injection attacks.

See also

• Covering system
• Residue number system

External links

• Chinese remainder theorem at cut-the-knot

References

• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.3.2 (pp.286–291), exercise 4.6.2–3 (page 456).
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.5: The Chinese remainder theorem, pp.873–876.
• Sigler, Laurence E. (trans.) (2002). Fibonacci's Liber Abaci. Springer-Verlag, 402–403. ISBN 0-387-95419-8. zh-classical:韓信點兵

Donate to Wikimedia