Page 256 - Hardware Implementation of Finite-Field Arithmetic

236 Cha pte r Ei g h t

multipliers described in Chap. 7. Sequential normal basis multipliers
for GF(2 ) are much more area efficient than their bit-parallel coun-
m
terparts, but in general take m iterations (or clock cycles) for one mul-
tiplication. Several methods have been proposed in the literature in
order to obtain efficient, normal basis multipliers ([HWB93], [RH00],
[RH02], [RH03a], [RH03b], [AA06], [WTSDOR85]).
On the other hand, Mullin et al. [MOVW88] gave a lower bound
on the complexity of normal bases and defined the normal bases
that have this lower bound as optimal normal bases. They defined two
special types of normal bases which are known as Type-I and Type-II
optimal normal bases [MBGMVY93]. Gao and Lenstra [GL92]
showed that all of these two types are the optimal normal bases in
m
GF(2 ). The use of these optimal normal bases can reduce consider-
ably the complexity of the different arithmetic operations ([BRS98],
[HWB93], [KKH03], [KS98], [RH00], [RH02], [RH03a], [RH03b],
[RH05], [YKPKL05], and [YL04]).

8.1 Some Properties of Normal Bases
m
Squaring in GF(2 ) is a linear operation. That is, given any two ele-
ments α and β in GF(2 ), (αβ+ ) = α + β 2 . Furthermore, as shown in
2
m
2
Chap. 1 for any element α ∈ GF(2 ), α 2 m = α. It is also readily seen
m
+
that 1 = +ββ 2 + β 4 ... + β 2 m − 1 for any element β in GF(2 ). This
m
implies that the normal basis representation of 1 is (1,1,1, . . . , 1).
Let N = {β 2 0 ,β 2 1 , ... ,β 2 m − 1 } be a normal basis of GF(2 ) over GF(2),
m
where the elements β , β , . . . , β 2 m − 1 are linearly independent over
1
0
2
2

GF(2). A polynomial in GF(2)[x] is called an N-polynomial if it is irre-
ducible and its roots are linearly independent over GF(2). It can be
proven that the elements in a normal basis are exactly the roots of an
N-polynomial. Hence, an N-polynomial is just another way of
describing a normal basis [MBGMVY93].
An important problem is: Given an integer m and the ground
m
field GF(2), construct a normal basis of GF(2 ) over GF(2), or equiva-
lently, construct an N-polynomial in GF(2)[x] of degree m. For practi-
cal applications, the normal basis should have a complexity as low as
possible. The construction of low complexity normal bases will be
treated later on in this chapter.
m
If β is a root of any irreducible polynomial f(x) = x + f m − 1 x m − 1
0
1
+ . . . + f x + f of degree m over GF(2), the powers β , β , . . . , β 2 m− 1
2
2
1 0
m
(i.e., the conjugates of β) are in GF(2 ) and constitute a complete set of
i
2
roots of f(x) [Wan86]. If these elements β , i = 0, . . . , m – 1, are linearly
m
independent, then they constitute a normal basis of GF(2 ) over GF(2)
[MBGMVY93]. In general, the linear independence of the roots of f(x)
is difficult to verify. A straightforward way to do this is as follows. Let
2
1
β be a root of f(x). Then {, , ββ ... , β m − 1 } form a polynomial basis of
,
GF(2 ) over GF(2) and β , β , . . . , β 2 m − 1 are all the roots of f(x) in
0
1
2
2
m