Page 281 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Normal Bases 261

5. r := y , 0 ≤ i ≤ m – 1, R := (r , r ,..., r )
i i,j 0 1 m-1
k
6. R:= R 2 j
7. C := C + R
8. f := f + y
j,v
9. end for
10. If f is 1 then
11. C := C + (1,1,...,1)
12. end if
Assume that k_array is defined as an array of integers from 1 to (m/2 – 1)
that holds the values k, with 1 ≤ j ≤ v – 1, computed using Eq. (8.40).
j
Then Algorithm 8.12 can be implemented as follows:
Algorithm 8.13—Type-I optimal normal basis multiplication with AOPs

v := m/2;
for i in 0 .. m-1 loop r(i) := 0; one(i) := 1; end loop;
for i in 0 .. m-1 loop
for j in 1 .. v loop
yij(i,j) := m2and(m2xor(a(i),a((i+j) mod m)),
m2xor(b(i),b((i+j) mod m)));
end loop;
end loop;
for i in 0 .. v-1 loop
yiv(i) := m2and(m2xor(a(i),a((v+i) mod m)),
m2xor(b(i),b((v+i) mod m)));
end loop;
for i in 0 .. m-1 loop
c(i) := m2and(a(i),b(i));
end loop;
f := yiv(0);
for j in 1 .. v-1 loop
for i in 0 .. m-1 loop
r(i) := yij(i,j);
end loop;
for i in 1 .. k(j) loop
r := NB_sq(r);
end loop;
c := m2xvv(c,r);
f := m2xor(f,yiv(j));
end loop;
if f = 1 then
c := m2xvv(c,one);
end if;
In Algorithm 8.13, the operation R := R is accomplished by a k -fold
k j
2
j
cyclic shift using normal basis squaring with an NB_sq function. An
executable Ada file NB_T1_multiplier.adb, including Algorithm 8.13,
is available at www.arithmetic-circuits.org.
A VHDL file NB_T1_multiplier.vhd, which models the Type-I
optimal normal basis multiplication given in Algorithm 8.13, is
available at www.arithmetic-circuits.org. The corresponding entity
declaration is