Page 185 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 167

The function
function reduction_matrix_R(f: poly_vector) return poly_
matrix_m1m2
computing the reduction matrix R can be implemented using
Eq. (7.7) as follows

for j in 0 .. m-1 loop
for i in 0 .. m-2 loop R(j,i) := 0; end loop;
end loop;
for j in 0 .. m-1 loop R(j,0) := f(j); end loop;
for i in 1 .. m-2 loop
for j in 0 .. m-1 loop
if j = 0 then R(j,i) := m2and(R(m-1,i-1),R(j,0));
else R(j,i) := m2xor(R(j-1,i-1),m2and(R(m-1,i-1),
R(j,0)));
end if;
end loop;
end loop;
return R;
where poly_matrix_m1m2 is an (m × m – 1) matrix of bits.
Finally, the two-step classic multiplication performing c(x) =
a(x)b(x) mod f(x) = d(x) mod f(x) using Eq. (7.6) and the reduction
matrix computed with Eq. (7.7) can be given, where the previously
defined functions poly_multiplication and reduction_matrix_R are
used.

Algorithm 7.1—Classic multiplication
d := poly_multiplication(a,b);
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_multiplication.adb, including Algorithm 7.1,
is available at www.arithmetic-circuits.org. Algorithm 7.1 is the binary
version of Algorithm 5.5.
A VHDL model for the classic multiplication algorithm (Algorithm
7.1) is given in the file classic_multiplier.vhd which is available at
www.arithmetic-circuits.org. This model includes two components
poly_multiplier and poly_reducer that implement the polynomial
multiplication and the reduction modulo f(x), respectively. The
datapaths for these two components are shown in Fig. 7.1.
The entity declaration of the classic multiplier given in the file
classic_multiplier.vhd is