Multiple-precision modular arithmetic

§14.2 provided methods for carrying out the basic operations (addition, subtraction, multiplication, squaring, and division) with multiple-precision integers. This section deals with these operations in Z,„, the integers modulo in, where m is a multiple-precision positive integer. (See §2.4.3 for definitions of ZTO and related operations.)

Let in = • • • 1Пто)ь be a positive integer in radix b representation. Let

x = (xnxn-i ■ ■ ■ ххо)ь and у = пУп-i • • • yiyo)b be non-negative integers in base b representation such that x < m and у < m. Methods described in this section are for computing x + у mod m (modular addition), x — у mod m (modular subtraction), and x ■ у mod m (modular multiplication). Computing x~l mod m (modular inversion) is addressed in §14.4.3.

14.26 Definition If г is any integer, then г mod m (the integer remainder in the range [0, in -1] after г is divided by in) is called the modular reduction of 2 with respect to modulus m.

As is the case for ordinary multiple-precision operations, addition and subtraction are the simplest to compute of the modular operations.

• 14.27 Fact Let x and у be non-negative integers with x, у < m. Then:
• (i) x + у < 2m;
• (ii) if x > y, then 0 < xу < m; and
• (iii) if x < y, then 0 < x + m — у < m.

If x, у € Zm, then modular addition can be performed by using Algorithm 14.7 to add a; and у as multiple-precision integers, with the additional step of subtracting in if (and only if) x + у > m. Modular subtraction is precisely Algorithm 14.9, provided x > y.

Classical modular multiplication

Modular multiplication is more involved than multiple-precision multiplication (§14.2.3), requiring both multiple-precision multiplication and some method for performing modular reduction (Definition 14.26). The most straightforward method for performing modular reduction is to compute the remainder on division by m, using a multiple-precision division algorithm such as Algorithm 14.20; this is commonly referred to as the classical algorithm for performing modular multiplication.

14.28 Algorithm Classical modular multiplication

INPUT: two positive integers x, у and a modulus m, all hi radix b representation. OUTPUT: x • у mod m.

• 1. Compute x ■ у (using Algorithm 14.12).
• 2. Compute the remainder r when x ■ у is divided by m (using Algorithm 14.20).
• 3. Retum(r).