Page 115 - Hardware Implementation of Finite-Field Arithmetic

98 Cha pte r F o u r

A complete VHDL file mult_subt.vhd is available at www.
arithmetic-circuits.org. The entity declaration is

entity mult_subt is
port (
c, d: in std_logic_vector (2*K-1 downto 0);
q: in std_logic_vector(K-1 downto 0);
clk, reset, start: in std_logic;
z: out std_logic_vector (2*K-1 downto 0);
done: out std_logic
);
end mult_subt;
The VHDL architecture corresponding to the circuit of Fig. 4.2 is
the following:
parallel_register: process(clk)
begin
if clk’event and clk = ‘1’ then
if load = ‘1’ then u <= c;
elsif update = ‘1’ then u <= dif(2*k downto 1);
end if;
end if;
end process parallel_register;
shift_register: process(clk)
begin
if clk’event and clk = ‘1’ then
if load = ‘1’ then v <= q;
elsif update = ‘1’ then
for i in 0 to k-2 loop v(i) <= v(i+1); end loop;
v(k-1) <= dif(0);
end if;
end if;
end process shift_register;
with v(0) select dif <= (u(2*K-1) & u) - (d(2*K-1) & d)
when ‘1’,
(u(2*k-1)&u) when others;
z <= u(K-1 downto 0)&v;

4.1.3 mod p Division
A datapath for executing Algorithm 4.1 is shown in Fig. 4.3.
T he nonrestoring divider and the multiplication-and-subtraction
circuits have been described in Secs. 4.1.1 and 4.1.2, respectively. The
reduction can be executed with the nonrestoring reducer of Sec. 2.1.2.
As a matter of fact the circuit of Sec. 2.1.2 computes x mod m where x
is an (n + 1)-bit 2’s complement integer and m a k-bit natural. As d is a
2k-bit integer, n = 2k − 1.
Let t be the number of executions of the main loop of Algorithm
4.1. The total computation time T is approximately equal to

T ≈ t(T + T ) + T (4.19)
division multiplication-and-subtraction reduction