Cryptography: 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 CRT is so called because it is believed to have been discovered by the Chinese mathematician Sun-Tsu in around 100 A.D.

•CRT says that in modulo M arithmetic, if M can be expressed as a product of n integers that are pairwise coprime, then every integer in the set ZM = {0, 1, 2, ...., M − 1} can be reconstructed from residues with respect to those n numbers.

•For example, the prime factors of 10 are 2 and 5. Now let’s consider an integer 9 in Z10. Its residue modulo 2 is 1 and the residue modulo 5 is 4. So, according to CRT, 9 can be represented by the tuple (1, 4).

 

 

 

Usefulness of CRT  

•CRT is extremely useful for manipulating very large integers in modulo arithmetic. We are talking about integers with over 150 decimal digits (that is, numbers potentially larger than 10150).

•Let’s say that we want to do arithmetic on integers modulo 8633. That is, M = 8633. This modulus has the following decomposition into two pairwise coprimes:

  8633 = 89×97
So we have m1 = 89 and m2 = 97. The corresponding Mi

Integers are M1 = M/m1 = 97 and M2 = M/m2 = 89.

•By using the Extended Euclid’s Algorithm we can next figure out the multiplicative inverse for M1 modulo m1 and the multiplicative inverse for M2 modulo m2.

M−11 mod m1 = 78

M−12 mod m2 = 12

•Now let’s say that we want to add two integers 2345 and 6789 modulo 8633.

•We first express the operand 2345 by its CRT representation, which is (31, 17) since 2345 mod 89 = 31 and 2345 mod 97 = 17.

•We next express the operand 6789 by its CRT representation, which is (25, 96) since 6789 mod 89 = 25 and 6789 mod 97 = 96.

•To add the two “large” integers, we simply add the two corresponding CRT tuples modulo the respective moduli. This gives us (56, 16). For the second of these two numbers, we initially get 113, which modulo 97 is 16.

•To recover the result as a single number, we use the formula

a1 × M1 × M−1 + a2 × M2 × M−1 mod M

which for our example becomes

56 × 97 × 78 + 16 × 89 × 12 mod 8633

that returns the result 501. You can verify this result by directly computing 2345 + 6789 mod 8633 and getting the same answer.