# 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 Z_{TO} and related operations.)

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

*x = (x _{n}x_{n}-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~*mod m

^{l}*(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.

Modular addition and subtraction

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.*

- (i)

If *x, у* € Z_{m}, 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).