Page 283 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Normal Bases 263

end loop;
for i in 0 to m-1 loop
c_v(i) := c_v(i) xor r(i);
end loop;
f := f xor yiv_s(j);
end loop;
if f = ‘1’ then
for i in 0 to m-1 loop
c_v(i) := not c_v(i);
end loop;
end if;
c_aux <= c_v;
end process;
c <= c_aux;
For Type-I optimal normal basis, another approach was given in
[KS98]. As stated, for Type-I optimal normal basis with an AOP as gen-
erating polynomial, the sets {,ββ 2 ,β 2 2 , ... ,β 2 m − 1 } and {,ββ 2 ,β 3 ,... ,β m }
2
3
are identical [MBGMVY93]. Furthermore, the basis {, ββ β ... ,β m }
, ,
is a shifted version of the polynomial basis. An element of the field
GF(2 ) in the normal basis representation can be converted to the
m
shifted polynomial representation using a permutation of the binary
coordinates. The root β of an AOP has the property of β m + 1 = 1. Hence
the conversion
m − 1 m
A = ∑ a β 2 i = ∑ a β′ i i (8.42)
i
i=0 i=1

can be performed using the following permutation [KS98]:

a′ = a for i = 01 ..., m 1− (8.43)
,,
+
i
2 mod( m 1) i
Therefore, in order to perform a Type-I optimal normal basis mul-
tiplication using this method, the inputs A and B represented in the
normal basis are taken. Then they must be converted to the shifted
polynomial basis using the permutation given in Eq. (8.43), and a
polynomial basis multiplication for AOPs is performed using the
equations and algorithms given in Chap. 7 (Section 7.6.3). At the end
2
of this computation, the result F = AB/β is obtained and represented
in the polynomial basis as

F = f + f β + f β 2 + ... + f β m − 1 (8.44)
0 1 2 m − 1

where the coefficients f s are the outputs of the polynomial basis
i
multiplier given in Section 7.6.3. Using Eq. (7.60), the coefficients