Home | | Cryptography and Network Security | The Chinese Remainder Theorem

# The Chinese Remainder Theorem

One of the most useful results of number theory is the Chinese remainder theorem (CRT). In essence, the CRT says it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli.

THE CHINESE REMAINDER THEOREM

One of the most useful results of number theory is the Chinese remainder theorem (CRT). In essence, the CRT says it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli.

The 10 integers in Z10, that is the integers 0 through 9, can be reconstructed from their two residues modulo 2 and 5 (the relatively prime factors of 10). Say the known residues of a decimal digit x are r2 = 0 and r5 = 3; that is, x mod 2 = 0 and x mod 5 = 3. Therefore, x is an even integer in Z10 whose remainder, on division by 5, is 3. The unique solution is x = 8.

The CRT can be stated in several ways. We present here a formulation that is most useful from the point of view of this text. An alternative formulation is explored in Problem 8.17. Let By the definition of Mi, it is relatively prime to mi and therefore has a unique multi- plicative inverse mod mi. So Equation (8.8) is well defined and produces a unique value ci. We can now compute One of the useful features of the Chinese remainder theorem is that it pro-vides a way to manipulate (potentially very large) numbers mod M in terms of tuples of smaller numbers. This can be useful when M is 150 digits or more. However, note that it is necessary to know beforehand the factorization of M. Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Cryptography and Network Security Principles and Practice : Asymmetric Ciphers : Introduction to Number Theory : The Chinese Remainder Theorem |