Chinese remainder theorem for integers
Fact 2.120 introduced the Chinese remainder theorem (CRT) and Fact 2.121 outlined an algorithm for solving the associated system of linear congruences. Although the method described there is the one found in most textbooks on elementary number theory, it is not the
iteration: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
u 
383 
112 
56 
28 
14 
7 
7 
7 
7 
7 
V 
271 
271 
271 
271 
271 
271 
264 
132 
66 
33 
в 
0 
1 
192 
96 
48 
24 
24 
24 
24 
24 
D 
1 
1 
1 
1 
1 
1 
25 
179 
281 
332 
iteration: 
11 
12 
13 
14 
15 
16 
17 
18 
19 

u 
7 
7 
7 
7 
4 
2 
1 
1 
1 

V 
2G 
13 
6 
3 
3 
3 
3 
2 
1 

в 
24 
24 
24 
24 
41 
171 
277 
277 
277 

D 
308 
154 
130 
65 
65 
65 
65 
212 
106 
Table 14.13: Inverse computation using the binary extended gcd algorithm (see Example 14.65).
method of choice for large integers. Garner’s algorithm (Algorithm 14.71) has some computational advantages. §14.5.1 describes an alternate (nonradix) representation for nonnegative integers, called a modular representation, that allows some computational advantages compared to standard radix representations. Algorithm 14.71 provides a technique for converting numbers from modular to base b representation.
Residue number systems
In previous sections, nonnegative integers have been represented in radix b notation. An alternate means is to use a mixedradix representation.
 14.66 Fact Let В be a fixed positive integer. Let mi, m2,... , m_{t} be positive integers such that gcd(rrii,mj) = 1 for all г ф j, and M = П1=1 ^{rn}> — Then each integer x, 0 < x < B, can be uniquely represented by the sequence of integers v(x) = (vi,V2,... , v_{t}), where Vi = x mod mi, 1 < i < t.
 14.67 Definition Referring to Fact 14.66, v(x) is called the modular representation or mixed radix representation of x for the moduli mi, m2,... , m_{t}. The set of modular representations for all integers x in the range 0 < x < В is called a residue number system.
 14.68 Fact If 0 < x, у < M, then v((x + y) mod M) = v(x) + v(y) and v((.x • y) mod M) = v(x) ■ v(y).
 14.69 Example (modular representation) Let M = 30 = 2 x 3 x 5; here, t = 3, mi = 2, m2 = 3, and m3 = 5. Table 14.14 displays each residue modulo 30 along with its associated modular representation. As an example of Fact 14.68, note that 21 + 27 = 18 (mod 30) and (101) + (102) = (003). Also 22 • 17 = 14 (mod 30) and (012) • (122) = (024). □
 14.70 Note (computational efficiency of modular representation for RSA decryption) Suppose that n = pq, where p and q are distinct primes. Fact 14.68 implies that x^{d} mod n can be computed in a modular representation as v^{d}(x) that is, if п(ж) = (vi, vf) with respect to moduli mi = p, m2 = q, then v^{d}(x) = (vf mod p, vij mod q). In general, computing
X 
v(x) 
X 
v(a;) 
X 
v(x) 
X 
v(a:) 
X 
v(x) 
0 
(000) 
G 
(001) 
12 
(002) 
18 
(003) 
24 
(004) 
1 
(111) 
7 
(112) 
13 
(113) 
19 
(114) 
25 
(110) 
2 
(022) 
8 
(023) 
14 
(024) 
20 
(020) 
2G 
(021) 
3 
(103) 
9 
(104) 
15 
(100) 
21 
(101) 
27 
(102) 
4 
(014) 
10 
(010) 
10 
(Oil) 
22 
(012) 
28 
(013) 
5 
(120) 
11 
(121) 
17 
(122) 
23 
(123) 
29 
(124) 
Table 14.14: Modular representations (see Example 14.69).
vf mod p and v^{d} mod q is faster than computing x^{d} mod n. For RSA, if p and q are part of the private key, modular representation can be used to improve the performance of both decryption and signature generation (see Note 14.75).
Converting an integer x from a base b representation to a modular representation is easily done by applying a modular reduction algorithm to compute v< = a; mod m_{4}, 1 < i < t. Modular representations of integers in Zм may facilitate some computational efficiencies, provided conversion from a standard radix to modular representation and back are relatively efficient operations. Algorithm 14.71 describes one way of converting from modular representation back to a standard radix representation.