Cryptographic Applications - Introduction to Cryptography with Java Applets - page 309

E XAMPLE .

Take the integer 73, and note that

73 9 (mod 64)

73 19 (mod 27)

73 23 (mod 25)

73 24 (mod 49).

We can thus represent the integer 73 as the vector

(9, 19, 23, 24)

where the moduli are here understood to be 64, 27, 25, and 49. There is no other positive
integer less than M = 64 27 25 49 = 2116800 that is represented by this vector. In fact,
every integer between 0 and 2116799 has a unique such representation.
This motivates us to consider perhaps representing integers in this way; we can do arith-
metic with such integers by instead doing the arithmetic with their smaller residues.

E XAMPLE .

We take now the integer 1907833, and note that

1907833 57 (mod 64)

1907833 13 (mod 27)

1907833 8 (mod 25)

1907833 18 (mod 49).

Using this representation, and the representation of 73 given earlier, we can then com-
pute 1907833 73 by computing

57 9 48 (mod 64)

13 19 = 6 21 (mod 27)

8 23 = 15 10 (mod 25)

18 24 = 6 43 (mod 49)

This gives the vector

(1, 4, 9, 40)

which is, in fact, the decomposed representation of 1907760 = 1907833 73. Taking the

lnr of 1907760 modulo, each of the moduli easily checks this. We can multiply, add, and sub-
tract (as long as the result of the subtraction is nonnegative) with numbers as large as
M

1 = 2116799 using this mixed radix representation. This works because of propositions
20 and 21.