Page 83 - Hardware Implementation of Finite-Field Arithmetic

66 Cha pte r T h ree

sel <= (not(addb_sub) and (c1 or c2)) or (addb_sub and
not(c1));
with sel select z <= z1 when ‘0’, z2 when others;

3.4 Multiplication mod m
Gi ven x and y ∈ Z = {0, 1, . . . , m − 1}, compute z = xy mod m, where
m
m is a k-bit natural.
3.4.1 Multiply and Reduce
As already quoted above, a straightforward method consists of
multiplying x by y, so that a 2k-bit result product is obtained, and then
reducing product mod m. For that, any combination of multiplier and
mod m reducer can be used. Nevertheless the chosen option should
be coherent. Two examples will be described.
For relatively small values of m, combinational circuits can be
considered for both the multiplication and the reduction. As an
example, synthesize a mod 239 multiplier. Any 8-by-8 parallel
multiplier can be used along with the mod 239 reducer of Fig. 2.10. A
VHDL file mod_239_multiplier.vhd is available at www.arithmetic-
circuits.org. The corresponding entity declaration is

entity mod_239_multiplier is
port (
x, y: in std_logic_vector(7 downto 0);
z: out std_logic_vector(7 downto 0)
);
end mod_239_multiplier;

The VHDL architecture corresponding to the circuit of Fig. 3.4 is
the following:

product <= x*y;
reducer_component: mod_239_reducer port map(product, z);
As a second example consider the case of a generic k-bit mod m
multiplier. Among the different mod m reduction circuits presented
in Chap. 2, one of the fastest is the SRT reducer of Sec. 2.1.3. Its main
computation resource is a carry-save adder ([Par00], [EL04], [DBS06]).
The multiplier that computes product should also be a fast one, for
example a sequential carry-save multiplier. The following shift-and-
add algorithm computes product = xy:
Algorithm 3.5—Shift and add multiplication

p(0) := 0;
for i in 0 .. k-1 loop
p(i+1) := (p(i) + x(i)*y)/2;
end loop;
product := p(n)*(2**n);