Page 80 - Hardware Implementation of Finite-Field Arithmetic

mod m Operations 63

3.2 Subtraction mod m
Given two natural numbers x and y belonging to Z = {0, 1, . . . , m − 1},
m
compute z = (x − y) mod m. Taking into account that
− m < x − y < m

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

Algorithm 3.3—mod m subtraction
z1 := x - y; z2 := z1 + m;
if z1 < 0 then z := z2; else z := z1; end if;
Algorithm 3.3 is slightly modified in order to get a more efficient
circuit. Assume that m is a k-bit natural and define
z = (x – y + 2 ) mod 2 k (3.3)
k
1
(instead of z − m). Then consider two cases:
1
k
k
If −m < x – y < 0 , then z = x – y + 2 < 2 ,
1
k
z = z + m = x – y + 2 + m > 2
k
2 1
k
z mod 2 = x – y + m
2
If 0 ≤ x – y < m, then 2 ≤ x – y + 2 < 2 + m, z = x – y
k
k
k
1
k
k
k
k
To summarize, either x – y + 2 < 2 and z = z mod 2 , or 2 ≤ x – y +
2
2 and z = z . The corresponding algorithm is the following:
k
1
Algorithm 3.4—Binary mod m subtraction
sum := x + (2**k - y);
z1 := (sum mod 2**k); c1 := sum/2**k;
z2 := (z1 + m) mod 2**k;
if c1 = 1 then z := z1; else z := z2; end if;
An executable Ada file binary_mod_m_subtraction.adb, including
Algorithm 3.4, is available at www.arithmetic-circuits.org.
Example 3.2 Assume that k = 8, m = 239.
x = 159 and y = 238: sum = 159 + 18 = 177, z = 177, z = 177 + 239 =
1 2
416, c = 0, z = z mod 256 = 160
1 2
x = 238 and y = 159: sum = 238 + 97 = 335, z = 79, z = 79 + 239 =
1 2
318, c = 1, z = z = 79
1 1
A combinational circuit implementing Algorithm 3.4 is shown in
Fig. 3.2. If ripple-carry adders are used, then its computation time is
equal to
T = T + (k + 1)T + T ≈ kT (3.4)
inv FA mux2 − 1 FA