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 ***r***2 ****= ****0 and ***r***5 ****= ****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 |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.