## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 8.1 OPERATIONS IN Zm

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

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 + ym. The corresponding algorithm is the following.

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

Assume now that Bn−1 < mBn 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 Bnm = 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required