Chapter: Cryptography and Network Security Principles and Practice : Asymmetric Ciphers : Introduction to Number Theory
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 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.
Related Topics