Page 102 - Hardware Implementation of Finite-Field Arithmetic

mod m Operations 85

Algorithm 3.15—Base 2 mod m exponentiation, LSB-first
e := 1;
for i in 0 .. k-1 loop
if binary_x(i) = 1 then e := (e*y) mod m; end if;
y := (y*y) mod m ;
end loop;
z := e;
An executable Ada file mod_m_exponentiation_lsb.adb, including
Algorithm 3.15, is available at www.arithmetic-circuits.org.
As before, the Montgomery product can substitute the mod m
product.

Algorithm 3.16—Base 2 mod m exponentiation (Montgomery product),
LSB-first

e := exp_k;
ty := mp(y, exp_2k);
for i in 0 .. k-1 loop
if binary_x(i) = 1 then e := mp(e, ty); end if;
ty := mp(ty, ty);
end loop;
z := mp(e, 1);

Algorithm 3.16 mainly consists of k executions of a loop that in turn
includes at most two Montgomery products. In this case both products
can be executed in parallel. A datapath corresponding to Algorithm
3.16 is shown in Fig. 3.11. According to Eq. (3.24) the computation
time of a Montgomery product is about 3kT , so that the total
FA
x
computation time of y mod m is approximately equal to
2
T ≈ 3k T (3.27)
FA
A complete VHDL file Montgomery_exponentiator_lsb.vhd is
available at www.arithmetic-circuits.org. The entity declaration is
entity Montgomery_exponentiator_lsb 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_lsb;
Th e VHDL architecture corresponding to the circuit of Fig. 3.11 is

with last select second <= ty when ‘0’, one when others;
with first select operand1 <= y when ‘1’, ty when others;
with first select operand2 <= exp_2k when ‘1’, ty when
others;