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.

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