Page 224 - Hardware Implementation of Finite-Field Arithmetic

204 Cha pte r Se v e n

when 8 => if count = N-1 then current_state <= 9;
else current_state <= 6; end if;
when 9 => current_state <= 10; --Adjust B= B/R
when 10 => current_state <= 11;
when 11 => current_state <= 12;
when 12 => if (done_mult = ‘1’) then current_state
<= 0; end if;
end case;
end if;
end process control_unit;

An iterative implementation is also given in the VHDL file
exponentiation_montgomery_adv.vhd, that can be found at www.
arithmetic-circuits.org. It must be noted that the combinational
squarer module used in this iterative circuit has a significant delay;
therefore squaring has to be performed in two clock cycles. For this
reason, a counter is used in such a way that when the count value is
two, a done signal will be activated.

7.4 Division
m
The quotient of two polynomials in GF(2 ) can be computed using
the binary version of the binary algorithm. The binary algorithm for
computing z(x) = g(x)h − 1 (x) mod f(x) has been described in Sec. 6.2
(Algorithm 6.5). If p = 2, it can be simplified.

Algorithm 7.19—Binary algorithm with p = 2
a := f; b := h; c := zero; d := g; alpha := m; beta :=
m-1;
while beta >= 0 loop
if b(0) = 0 then
b := shift_one(b); d := divide_by_x(d, f); beta :=
beta - 1;
else
old_b := b; old_d := d; old_beta := beta;
b := shift_one(add(a, b));
d := divide_by_x(add(c, d),f);
if alpha > beta then
a := old_b; c := old_d; beta := alpha - 1; alpha :=
old_beta;
else beta := beta - 1;
end if;
end if;
end loop;
z := c;