Page 128 - Hardware Implementation of Finite-Field Arithmetic

Operations over GF ( p ) 111

x y
exp_2k
cont 2 0 1 e e txy 1

x
00 01,10,11 00 01 10 11 cont 1
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
z k–i
result

k-bit register ce ce_e k-bit register ce ce_txy
initially: exp_k load load

e txy
FIGURE 4.6 Divider based on the Fermat’s little theorem.

A complete VHDL file Fermat_divider.vhd is available at www.
arithmetic-circuits.org. The entity declaration is

entity Fermat_divider 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 Fermat_divider;

The VHDL architecture corresponding to the circuit of Fig. 4.6 is
the following:

with cont1 select operand1 <= xy when “00”, e when
others;
with cont1 select operand2 <= EXP_2K when “00”,
e when “01”, txy when “10”, ONE when others;
with cont2 select xy <= x when ‘0’, y when others;
main_component: Montgomery_multiplier
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;