Page 301 - Discrete Mathematics and Its Applications

280 4 / Number Theory and Cryptography
EXAMPLE 8
To perform arithmetic with large integers, we select moduli m 1 ,m 2 ,...,m n , where each m i
is an integer greater than 2, gcd(m i ,m j ) = 1 whenever i = j, and m = m 1 m 2 ··· m n is greater
than the results of the arithmetic operations we want to carry out.
Once we have selected our moduli, we carry out arithmetic operations with large integers by
performing componentwise operations on the n-tuples representing these integers using their
remainders upon division by m i ,i = 1, 2,...,n. Once we have computed the value of each
component in the result, we recover its value by solving a system of n congruences modulo
m i ,i = 1, 2,...,n. This method of performing arithmetic with large integers has several valu-
able features. First, it can be used to perform arithmetic with integers larger than can ordinarily
be carried out on a computer. Second, computations with respect to the different moduli can be
done in parallel, speeding up the arithmetic.
Suppose that performing arithmetic with integers less than 100 on a certain processor is much
quicker than doing arithmetic with larger integers. We can restrict almost all our computations to
integers less than 100 if we represent integers using their remainders modulo pairwise relatively
prime integers less than 100. For example, we can use the moduli of 99, 98, 97, and 95. (These
integers are relatively prime pairwise, because no two have a common factor greater than 1.)
By the Chinese remainder theorem, every nonnegative integer less than 99 · 98 · 97 · 95 =
89,403,930 can be represented uniquely by its remainders when divided by these four mod-
uli. For example, we represent 123,684 as (33, 8, 9, 89), because 123,684 mod 99 = 33;
123,684 mod 98 = 8; 123,684 mod 97 = 9; and 123,684 mod 95 = 89. Similarly, we represent
413,456 as (32, 92, 42, 16).
To find the sum of 123,684 and 413,456, we work with these 4-tuples instead of these two
integers directly. We add the 4-tuples componentwise and reduce each component with respect
to the appropriate modulus. This yields
(33, 8, 9, 89) + (32, 92, 42, 16)
= (65 mod 99, 100 mod 98, 51 mod 97, 105 mod 95)
= (65, 2, 51, 10).
To find the sum, that is, the integer represented by (65, 2, 51, 10), we need to solve the
system of congruences
x ≡ 65 (mod 99),
x ≡ 2 (mod 98),
x ≡ 51 (mod 97),
x ≡ 10 (mod 95).
It can be shown (see Exercise 53) that 537,140 is the unique nonnegative solution of this
system less than 89,403,930. Consequently, 537,140 is the sum. Note that it is only when we
have to recover the integer represented by (65, 2, 51, 10) that we have to do arithmetic with
integers larger than 100. ▲
Particularly good choices for moduli for arithmetic with large integers are sets of integers of
k
the form 2 − 1, where k is a positive integer, because it is easy to do binary arithmetic modulo
such integers, and because it is easy to find sets of such integers that are pairwise relatively prime.
b
a
[The second reason is a consequence of the fact that gcd(2 − 1, 2 − 1) = 2 gcd(a, b) − 1, as
Exercise 37 in Section 4.3 shows.] Suppose, for instance, that we can do arithmetic with integers
less than 2 35 easily on our computer, but that working with larger integers requires special
procedures. We can use pairwise relatively prime moduli less than 2 35 to perform arithmetic
with integers as large as their product. For example, as Exercise 38 in Section 4.3 shows, the
integers 2 35 − 1, 2 34 − 1, 2 33 − 1, 2 31 − 1, 2 29 − 1, and 2 23 − 1 are pairwise relatively prime.
Because the product of these six moduli exceeds 2 184 , we can perform arithmetic with integers
as large as 2 184 (as long as the results do not exceed this number) by doing arithmetic modulo
35
each of these six moduli, none of which exceeds 2 .