Page 101 - Hardware Implementation of Finite-Field Arithmetic

84 Cha pte r T h ree

The VHDL architecture corresponding to the circuit of Fig. 3.10 is
with control select operand1 <= y when “00”, e when
others;
with control select operand2 <= exp_2k when “00”, e when
“01”, ty when “10”, one when others;
main_component: Montgomery_multiplier_modif port
map(operand1, operand2, clk, reset, start_mp, result,
mp_done);
z <= result;
register_e: process(clk)
begin
if clk’event and clk = ‘1’ then
if load = ‘1’ then e <= exp_k;
elsif ce_e = ‘1’ then e <= result;
end if;
end if;
end process register_e;
register_ty: process(clk)
begin
if clk’event and clk = ‘1’ then
if ce_ty = ‘1’ then ty <= result; end if;
end if;
end process register_ty;
shift_register: process(clk)
begin
if clk’event and clk = ‘1’ then
if load = ‘1’ then int_x <= x;
elsif update = ‘1’ then
int_x <= int_x(K-2 downto 0)&’0’;
end if;
end if;
end process shift_register;
xkminusi <= int_x(K-1);

Algorithm 3.14 mainly consists of k executions of a loop that in turn
includes at most two Montgomery products. According to Eq. (3.24)
the computation time of a Montgomery product is about 3kT , so that
FA
the total computation time of y mod m is approximately equal to
x
2
T ≈ 6k T (3.25)
FA
Another way to compute z = y mod m is given by the following
x
expression

z = y 0 ( y ) ( y ) ... y ( 2 k−1 ) x k− 1 mod m (3.26)
x
x
x
2
2
2
2
1
to which corresponds the following algorithm: