Discover

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

Contents

Theorem statement

A constructive algorithm to find the solution

Statement for principal ideal domains

Statement for general rings

Applications

See also

External links

References

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
:
x &equiv a_1 pmod{n_1} \
x &equiv a_2 pmod{n_2} \
&dots \
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:
:$a\_i\; equiv\; a\_j\; pmod\{gcd(n\_i,n\_j)\}\; qquad\; mbox\{for\; all\; \}imbox\{\; and\; \}j\; .\; ,!$
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:
:$x\; equiv\; a\_i\; pmod\{n\_i\}\; quadmathrm\{for\};\; i\; =\; 1,\; ldots,\; k.$
Again, to begin, the product $N=n\_1n\_2ldots\; 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:
:$r\_i\; n\_i\; +\; e\_i\; =\; 1\; ,!$
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$
e i.
:$e\_i\; equiv\; 1\; pmod\{n\_i\}\; quad\; mathrm\{and\}\; quad\; e\_i\; equiv\; 0\; pmod\{n\_j\}\; quad\; mathrm\{for\}\; ~\; i$
e j
Because of this, combined with the multiplication rules allowed in congruences, one solution to the system of simultaneous congruences is:
:$x\; =\; sum\_\{i=1\}^k\; a\_i\; e\_i.$
For example, consider the problem of finding an integer ''x'' such that
:$x\; equiv\; 2\; pmod\{3\},\; ,!$
:$x\; equiv\; 3\; pmod\{4\},\; ,!$
:$x\; equiv\; 1\; pmod\{5\}.\; ,!$
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\_1$, $e\_2$, and $e\_3$. 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
:$f\; :\; R/uR$
ightarrow R/u_1R imes cdots imes
R/u_k R
such that
:$f(x\; +uR)\; =\; (x\; +\; u\_1R,\; ldots\; ,\; x\; +u\_kR)\; quadmbox\{\; for\; every\; \}\; xin\; R.$
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
:$r\; u\_i\; +\; s\; u/u\_i\; =\; 1.\; ,!$
Set ''e_i'' = ''s u/u_i''. Then the inverse of ''f'' is the map
:$g\; :\; R/u\_1R\; imes\; cdots\; imes\; R/u\_kR$
ightarrow R/uR
such that
:$g(a\_1+u\_1R,ldots\; ,a\_k+u\_kR)=$
left( sum_{i=1}^k a_i e_i
ight) + uR quadmbox{ for all }a_1,ldots,a_kin R.
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
:$x\; equiv\; a\_i\; pmod\{u\_i\}\; quadmathrm\{for\};\; i\; =\; 1,\; ldots,\; k$
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
:$f\; :\; R/I$
ightarrow R/I_1 imes cdots imes R/I_k
such that
:$f(x\; +\; I)\; =\; (x\; +I\_1,\; ldots\; ,\; x+I\_k)\; quadmbox\{\; for\; all\; \}\; xin\; R.$

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 $Bbb\{Z\}\_n$ to the ring $Bbb\{Z\}\_p\; imes\; Bbb\{Z\}\_q$. 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.

★ Fibonacci's Liber Abaci, Sigler, Laurence E. (trans.), , , Springer-Verlag, 2002, ISBN 0-387-95419-8