Page 70 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 53

begin
if z3(194) = ‘0’ then z <= z3(191 downto 0);
elsif z2(193) = ‘0’ then z <= z2(191 downto 0);
elsif z1(192) = ‘0’ then z <= z1(191 downto 0);
else z <= s(191 downto 0);
end if;
end process;

The algorithm can be slightly modified in order to reduce the
cost. According to Eq. (2.59), s is a 194-bit number that can be
decomposed under the form

s = (s · 2 + s )2 192 + s · 2 + . . . + s · 2 + s
191
193 192 191 1 0
191
≡ (s · 2 + s )(2 + 1) + s 2 + . . . + s · 2 + s
64
193 192 191 1 0
Then define
64
65
s’ = s · 2 + s · 2 + s · 2 + s
193 192 193 192
191
s’’ = s 2 + . . . + s · 2 + s
191 1 0
Thus
s ≡ ss = s’ + s’’ (2.60)
An upper limit for ss is given by
64
192
ss < 2 + 2 + 2 + 3 < 2(2 – 2 − 1) (2.61)
64
65
192
64
192
so that x mod (2 − 2 − 1) is either
192
64
ss or ss – (2 − 2 − 1)
The corresponding circuit is shown in Fig. 2.12.
A VHDL file mod_p192_reducer.vhd is available at www.
arithmetic - circuits.org. The VHDL architecture corresponding to the
circuit of Fig. 2.12 is the following:
xx1 <= x(383 downto 320) & x(383 downto 320) & x(383 downto
320);
xx2 <= x(319 downto 256) & x(319 downto 256) & ZEROS64;
xx3 <= ZEROS64 & x(255 downto 192) & x(255 downto 192);
xx4 <= x(191 downto 0);
xx12 <= (‘0’ & xx1) + xx2;
xx34 <= (‘0’ & xx3) + xx4;
s <= (‘0’ & xx12 + xx34);
ss <= (‘0’ & s(191 downto 0))+
(s(193 downto 192) & ZEROS62 & s(193 downto 192));
zz <= ss + minus_p;
with zz(192) select z <= ss(191 downto 0) when ‘1’,
zz(191 downto 0) when others;