Page 50 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 33

csa: for i in N-K to N generate
rs(i) <= ss(i) xor sc(i) xor w(i-N+K);
rc(i+1) <=
(ss(i) and sc(i)) or (ss(i) and w(i-N+K)) or (sc(i) and
w(i-N+K)) ;
end generate;
rs(N+1) <= ss(N+1) xor sc(N+1) xor w(K+1);
rs(N-K-1 downto 0) <= ss(N-K-1 downto 0);
r(0) <= rs(N-K);
r(K downto 1) <= rs(N downto N-k+1)+rc(N downto N-K+1);
with r(K) select z <= r(K-1 downto 0) when ‘0’,
r(K-1 downto 0)+m when others;
registers: process(clk)
begin
if clk’event and clk=‘1’ then
if load = ‘1’ then ss <= x(N)&x(N)&x; sc <= (others => ‘0’);
elsif update=‘1’ then
ss(0) <= ‘0’;
for i in 1 to N+2 loop ss(i) <= rs(i-1); end loop;
sc(N-K) <= ‘0’; sc(N-K+1) <= ‘0’;
for i in N-K+2 to N+2 loop sc(i) <= rc(i-1); end loop;
end if;
end if;
end process registers;
t <= ss(N+2 downto N-1)+sc(N+2 downto N-1);
quotient(1) <= t(3) xor (t(2) and t(1) and t(0));
quotient(0) <= not(t(2) and t(1) and t(0));
not_gates: for i in 0 to K-1 generate
not_m(i) <= not(m(i));
end generate;
minus_m <= (“11”¬_m) +1;
with quotient select w <= minus_m when “01”, (“00”&m) when
“11”,
(others => ‘0’) when others;
The complete model additionally includes an (n − k) − state counter
and a control unit generating the load, update, and done signals.

Comment 2.1 It is important to note that in the preceding VHDL
description the done signal is raised at the end of the main loop of
Algorithm 2.2, that is, when the execution of the final operations
(those which are not executable in one clock cycle) begins. For the
done signal to be raised when the final result z is actually available,
some kind of synchronization of the final operations should be
introduced, and the control unit modified accordingly.

2.2 Reduction mod 2 − a
k
Assume that

k
2 k − 1 ≤ m < 2 (2.21)