Page 266 - Hardware Implementation of Finite-Field Arithmetic

246 Cha pte r Ei g h t

21. r := y ((i w v,k )),v , 0 ≤ i ≤ t − 1
−
i
22. if m is even then
23. r := r , 0 ≤ i ≤ m / 2 - 1
i+ m i
2
24. R := ( r,r ,... ,r m/2 − ,r,r ,... ,r m/2 − )
0 1 1 0 1 1
25. end if
26. T := T + R
27. end for
28. C := C + T
Assume that h_array is defined as an array of integers from 1 to
m/2 holding the values h , with 1 ≤ j ≤ v, representing the number
j
of nonzero coordinates of the normal basis representation of δ .
j
Assume that w_array is an array of integers (1 . . . m/2, 1 . . . m – 1)
holding the values w , with 1 ≤ j≤ v, 1 ≤ k≤ h , where w , w ,... , w
,
j,k j j,1 j,2 j h j
denote the positions of the nonzero coordinates in the normal basis
representation of δ . Then Algorithm 8.3 can be implemented as
j
follows:
Algorithm 8.4—Normal basis multiplication in GF(2 )
m
v := m/2;
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 .. m-1 loop c(i) := m2and(a(i),b(i));
end loop;
for j in 1 .. v-1 loop
for i in 0 .. m-1 loop t(i) := 0; end loop;
for k in 1 .. h(j) loop
for i in 0 .. m-1 loop r(i) := yij((i-w(j,k)) mod m,j);
end loop;
t := m2xvv(t,r);
end loop;
c := m2xvv(c,t);
end loop;
for i in 0 .. m-1 loop t(i) := 0; end loop;
if (m rem 2) /= 0 then s := h(v); te := m;
else s := h(v)/2; te := m/2;
end if;
for i in 0 .. te-1 loop
yij(i,v) := m2and(m2xor(a(i),a((v+i) mod m)),
m2xor(b(i),b((v+i) mod m)));
end loop;
if (m rem 2) = 0 then
for i in 0 .. (m/2)-1 loop yij(i+v,v) := yij(i,v);
end loop;
end if;
for k in 1 .. s loop