Page 65 - Hardware Implementation of Finite-Field Arithmetic

48 Cha pte r T w o

if ce_r = ‘1’ then r <= dif(k+1 downto 0); end if;
end if;
end process;
z <= r(k-1 downto 0);

2.5 Comparison
Throughout this chapter five reduction algorithms were considered:
k
nonrestoring division, SRT division, mod 2 − a reduction, pre-
ik
computation of 2 mod m, and Barrett algorithm. The corresponding
approximate computation times are shown in Table 2.1 [Eqs. (2.15),
(2.20), (2.32), (2.36), and (2.51)]:
Reduction algorithm Computation time
Nonrestoring k(n − k)T
FA
SRT (5n − 4k + 6)T
FA

k
mod 2 −a (n − k + 1)nT
MULT
Precomputation 2nT
MULT
Barrett 5(n + 3)T
MULT
TABLE 2.1 Approximate Computation Times
The nonrestoring reducer includes one k-bit adder and one (n + 2)-
bit register. Its cost is a linear function of k and n. The SRT-reducer
includes two k-bit adders and one (n + k + 2)-bit register. Its cost is also
a linear function of k and n. The other reducers include a multiplier:
k
an (n − k)-bit by k-bit multiplier in the case of the mod 2 − a, a k-bit by
k-bit multiplier in the case of the precomputation, and an n -bit by
1
n -bit multiplier, where n = max{n − k + 1, k + 2} and n = max{n − k +
2 1 2
1, k}, in the case of the Barrett reducer.
An interesting particular case is when n ≈ 2k (see Table 2.2). It
corresponds, among others, to the second step of a straightforward
method for computing the product xy mod m where x, y, and m are
k-bit numbers: first compute z = xy, a 2k-bit number, and after that
reduce z mod m. In the case of the Barrett reducer, with n ≈ 2k, both
numbers of bits n and n are approximately equal to k.
1 2

Reduction algorithm Computation time k-by-k multiplier
Nonrestoring k T No
2
FA
SRT 6kT No
FA
2
k
mod 2 − a 2k T Yes
MULT
Precomputation 4kT Yes
MULT
Barrett 10kT Yes
MULT
TABLE 2.2 Approximate Computation Times when n ≈ 2k