Page 88 - Hardware Implementation of Finite-Field Arithmetic

mod m Operations 71

Algorithm 3.6—Double, add, and reduce
p := 0 ;
for i in 0 .. k-1 loop
p := (p*2 + x(k-i-1)*y) mod m;
end loop;
product := p;
In the following equivalent algorithm, the function mod_m_
addition(x, y, m, k) computes x + y mod m; x, y, and m being k-bit
numbers, according to Algorithm 3.2:

Algorithm 3.7—Double, add, and reduce (second version)
;
p := 0
for i in 0 .. k-1 loop
p := mod_m_addition(p, p, m, k);
if x(k-i-1) = 1 then p := mod_m_addition(p, y, m, k);
end if;
end loop;
product := p;

An executable Ada file dar_mod_multiplication, including Algorithm
3.7, is available at www.arithmetic-circuits.org.
The datapath corresponding to Algorithm 3.7 is shown in Fig. 3.7.
The combinational circuit generates

=
∨
_
_
(
condition ce p∧( step type x i))
y
0 1 step_type
ce_p
m

x y m
mod m adder
(Fig. 3.2)
x
z

condition comb.
ce k- bit shift shift update
k- bit register circ. register
clear load x (i) load load
p

z
FIGURE 3.7 Double, add, and reduce multiplier.