Page 279 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Normal Bases 259

t := NB_multiplier(p,q,h,w);
if r(0) = 1 then
t := NB_sq(t);
p := NB_multiplier(t,a,h,w);
else
p := t;
end if;
end loop;
p := NB_sq(p);
l := p;

In Algorithm 8.11, the bit ordering used is from 0 to (m – 1). Therefore,
lshift and NB_sq functions are used for the shift and rotate operations
given in Algorithm 8.10. An executable Ada file NB_Itoh_Tsujii_inv.adb,
including Algorithm 8.11, is available at www.arithmetic-circuits.org.

8.6 Optimal Normal Bases
m
In Sec. 8.3, the complexity of a normal basis N of GF(2 ) over GF(2)
was defined in Eq. (8.17) by C = H(M ), with 0 ≤ i ≤ m – 1. It can be
N i
proven ([MBGMVY93], [MOVW88]) that the complexity of a nor-
mal basis is lower bounded by C ≥ 2m – 1. Therefore, normal bases
N
with C = 2m – 1 are said to be optimal normal bases.
N
Normal bases of low complexity are desirable in hardware or
software implementations of finite fields. Only the following two
optimal normal bases [MBGMVY93] exist in GF(2 ):
m
Type-I optimal normal basis: m + 1 is a prime p and 2 is a primitive
modulo p (namely, the multiplicative order of 2 modulo p is m).
Type-II optimal normal basis: 2m + 1 is a prime p and either
a. 2 is a primitive modulo p, or
b. p ≡ 3 (mod 4) and the multiplicative order of 2 modulo p is m
(namely, 2 generates the quadratic residues of modulo p).

Type-I optimal normal basis is generated by elements β ∈ GF(2 )
m
of order p = m + 1. It can be observed that the minimal polynomial of
m
m-1
β is the AOP (all-one-polynomial, studied in Chap. 7) f(x) = x + x
+ . . . + x + 1 and the sets {,ββ 2 ,β 2 2 ,... ,β 2 m − 1 } and {,ββ 2 ,β 3 ,... ,β m } are
identical [MBGMVY93]. Thus, after suitable permutation, we can
operate on elements in optimal normal basis representation as poly-
m
2
nomials modulo f(x). Results expressed in terms of 1, β, β , . . . , β can
be brought back to the desired basis set by using, when needed, the
2
m
equality 1 = β + β + . . . + β . So, in addition to being attractive for
hardware applications, the Type-I optimal normal basis representa-
tion inherits the advantages of the polynomial representation.
Type-II optimal normal basis is constructed using the normal ele-
−1
ments β = γ+ γ [MBGMVY93], where γ is a primitive (2m + 1)th root
of unity, that is, γ 2m + 1 = 1 and γ ≠ 1 for any 1 ≤ i < 2m + 1. A Type-II
i