Page 100 - Hardware Implementation of Finite-Field Arithmetic

mod m Operations 83

Algorithm 3.14—Base 2 mod m exponentiation, MSB-first (Montgomery product)
e := exp_k;
ty := mp(y, exp_2k);
for i in 1 .. k loop
e := mp(e, e);
if binary_x(k-i) = 1 then e := mp(e, ty); end if;
end loop;
z := mp(e, 1);
An executable Ada file Montgomery_exponentiation_msb.adb,
including Algorithm 3.14 is available at www.arithmetic-circuits.org.
A datapath corresponding to Algorithm 3.14 is shown in Fig. 3.10.
In this circuit it is essential that the mp_done signal is raised when the
final result is available (Comment 2.1). For that, a modified model of
the Montgomery multiplier has been generated. It includes a timer
that delays the rising of the done signal. The delay is a parameter that
can be defined by the designer in function of the type of adder used
for the final steps. The modified model Montgomery_multiplier_
modif.vhd and the exponentiator model Montgomery_exponentiator_
msb.vhd are available at www.arithmetic-circuits.org. The declaration
of the entity Montgomery_exponentiator_msb is the following:
entity Montgomery_exponentiator_msb is
port (
x, y: in std_logic_vector(K-1 downto 0);
clk, reset, start: in std_logic;
z: out std_logic_vector(K-1 downto 0);
done: out std_logic
);
end Montgomery_exponentiator_msb;

exp_2k
y e e ty 1

x
00 01,10,11 00 01 10 11
control
operand 1 operand 2
parallel_in shift update
serial_out load load
x y
k-bit shift register
reset Montgomery start start_mp
multiplier
done mp_done x k–i
z
result
k-bit register ce ce_e k-bit register ce ce_ty
initially:exp_k load load

z
e ty
FIGURE 3.10 mod m exponentiation, MSB-fi rst algorithm.