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

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 (non-radix) 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, non-negative integers have been represented in radix b notation. An alternate means is to use a mixed-radix 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

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₄, 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.