Page 196 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 177

for i in 1 .. m-2 loop
for j in 0 .. m-1 loop
if j = 0 then P(i,j) := P(i-1,m-1);
else P(i,j) := m2xor(P(i-1,j-1),m2and(P(i-1,m-1),
P(0,j)));
end if;
end loop;
end loop;
return P;
where poly_matrix_m2m1 is a (m – 1 × m) matrix of bits. Assume also
that the function

function mastrovito_matrix (a: poly_vector; P: poly_
matrix_m2m1) return poly_matrix
computing the Mastrovito matrix Z also has been implemented using
Eq. (7.20) as follows
for i in 0 .. m-1 loop Z(i,0) := a(i); end loop;
for i in 0 .. m-1 loop
for j in 1 .. m-1 loop Z(i,j) := 0; end loop;
end loop;
for i in 0 .. m-1 loop
for j in 1 .. m-1 loop
for t in 0 .. j-1 loop
Z(i,j) := m2xor(Z(i,j),m2and(P(j-1-t,i),a(m-1-t)));
end loop;
if i >= j then Z(i,j) := m2xor(a(i-j),Z(i,j)); end if;
end loop;
end loop;
return Z;
where the P matrix has been previously computed and where poly_
matrix is a (m × m) matrix of bits. The Mastrovito multiplication in
Eq. (7.19) can therefore be given in the following algorithm, where
the functions matrix_P and mastrovito_matrix are used.

Algorithm 7.4—Mastrovito multiplication

for j in 0 .. m-1 loop C(j) := 0; end loop;
P := matrix_P(f);
Z := mastrovito_matrix(a,P);
for i in 0 .. m-1 loop
for j in 0 .. m-1 loop
C(i) := m2xor(C(i),m2and(Z(i,j),b(j)));
end loop;
end loop;
An executable Ada file mastrovito_multiplication.adb, including
Algorithm 7.4, is available at www.arithmetic-circuits.org.