Page 58 - Hardware Implementation of Finite-Field Arithmetic
P. 58
mod m Reduction 41
x
n-bit register load
initially (load): x n–1 , ... , x 0
after reload: acc reload
r r (d – 1..k)
NOR end_of_computation
sel
s-word k-bit
k s-to-1 multiplexers
look-up table
vector_r (sel) b sel
r (k – 1..0) m
k-bit by k-bit
multiplier
sign
product k-bit subtractor
d-bit adder 1 0
next_acc
d-bit register load
load and reload: z
acc = 0 reload
acc
ik
FIGURE 2.7 Data path of a reducer with precomputation of 2 mod m.
a (2)b (0) a (1)b (0) a (0)b (0)
a (2)b (1) a (1)b (1) a (0)b (1)
a (2)b (2) a (1)b (2) a (0)b (2)
HA FA HA
c (7) c (6) c (5) c (4) c (3) c (2) c (1) c (0)
HA HA FA FA FA FA FA HA
FIGURE 2.8 Carry-save multiplier and carry-ripple adders (k = 3 and d = 8).
