## 8.1 OPERATIONS IN *Z*_{m}

Given a natural number *m* > 1, the set *Z*_{m} = {0, 1, … , *m* − 1} is a ring whose operations are defined modulo *m* (Chapter 2):

### 8.1.1 Addition

Given two natural numbers *x* and *y* belonging to the interval 0 ≤ *x*, *y* < *m*, compute *z* = (*x + y*) mod *m*. Taking into account that

*z* must be equal to either *x* + *y* or *x* + *y* − *m*. The corresponding algorithm is the following.

**Algorithm 8.1 Modulo ***m* Addition

z1:=x+y; z2:=z1 − m;
**if** z2>=0 **then** z:=z2; **else** z:=z1; **end if;**

Assume now that *B*^{n−1} < *m* ≤ *B*^{n} and that *x* and *y* are *n*-digit base-*B* numbers. Consider three cases:

So Algorithm 8.1 can be substituted by the following one where all operands have *n* digits.

**Algorithm 8.2 Base ***B* Modulo *m* Addition

z1:=(x+y) mod B**n; c1:=(x+y)/B**n;
z2:=(z1+B**n - m) mod B**n; c2:=(z1+B**n - m)/B**n;
**if** c1=0 and c2=0 **then** z:=z1; **else** z:=z2; **end if;**

**Example 8.1** Assume that *B* = 10, *n* = 3, *m* = 750, so that *B*^{n} − *m* = 250:

### 8.1.2 Subtraction

Given two natural numbers *x* and *y* belonging to the interval 0 ≤ *x*, *y < m*, compute *z* = (*x − y*) mod *m*. Taking into account that

*z* must be equal to either *x − y* or *x − y + m ...*