Page 207 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 187

end case;
if reset = ‘1’ then current_state <= 0;
elsif clk’event and clk = ‘1’ then
case current_state is
when 0 => if start = ‘0’ then current_state <= 1;
end if;
when 1 => if start = ‘1’ then current_state <= 2;
end if;
when 2 => current_state <= 3;
when 3 => if count = M-1 then current_state <= 0;
end if;
end case;
end if;
end process control_unit;
A combinational implementation of this Montgomery multiplier
is also given in the VHDL file montg_comb_mult.vhd, that is available
at www.arithmetic-circuits.org.

7.2 Squaring
A straig htforward manner for implementing field squaring in GF(2 ) is
m
using the multiplication algorithms given in Sec. 7.1 with only one input
2
operand in order to perform c(x) = a(x)a(x) mod f(x) = a(x) mod f(x), that
is, the operand b(x) is substituted by a(x). For example, two-step classic
squaring could be implemented using the following algorithm:

Algorithm 7.9—Classic squaring

d := poly _multiplication(a,a);
R := reduction_matrix_R(f);
for j in 0 .. m-1 loop c(j) := d(j); end loop;
for j in 0 .. m-1 loop
for i in 0 .. m-2 loop
c(j) := m2xor(c(j),m2and(R(j,i),d(m+i)));
end loop;
end loop;

An executable Ada file classic_squaring.adb, including Algorithm 7.9,
is available at www.arithmetic-circuits.org.
MSB-first and LSB-first approache s for squaring can also be given
in a similar manner. For example, LSB-first squaring could be imple-
mented as follows:

Algorithm 7.10—LSB-first squaring
for i in 0 .. m-1 loop c(i) := 0; end loop;
for i in 0 .. m-1 loop
c := m2xvv(m2abv(aux(i),a),c);
a := Product_alpha_A(a,f);
end loop;