Page 255 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 8

Operations over

m
GF (2 )—Normal

Bases

hapter 8 deals with the study of the arithmetic operations
m
over the binary field GF(2 ), where the elements of the finite
Cfield are represented in a normal basis.
An element β∈ GF(2 ), N = {β 2 0 ,β 2 1 ,... ,β 2 m − 1 } is called a normal basis
m
of GF(2 ) over GF(2) if β , β , . . . , and β 2 m − 1 are linearly independent
0
1
2
2
m

([LN94], [MBGMVY93]). In such a case, we say that β generates the
m
normal basis N, or β is a normal element of GF(2 ) over GF(2). It is well
m
known that there exists a normal basis in the field GF(2 ) over GF(2) for
m
all positive integers m. Using a normal basis, any element A ∈ GF(2 )
can be represented as
m − 1
A = ∑ a β 2 i = a β + a β 2 + ... + a m − 1 β 2 m − 1 (8.1)
1
0
i
i=0
where a ∈ GF(2), 0 ≤ i ≤ m – 1 is the ith coordinate of A. In short, this
i
normal basis representation of A is written as A = (a , a , . . . , a ).
0 1 m − 1
The simplest arithmetic operation in normal basis is squaring, car-
ried out by a cyclic right shift, and hence almost free of cost in hard-
ware. Such a cost advantage often makes normal basis a preferred
choice of representation. However, a normal basis multiplication is not
so simple. A circuit design for the multiplication of two finite field
elements represented in a normal basis was first described by Massey
and Omura [MO86]. Due to their creators, normal basis multipliers
are sometimes referred to as Massey-Omura multipliers. Alt hough
the original description focuses on a bit-serial multiplier, bit-parallel
versions are easily constructed.
Bit-parallel normal basis multipliers for GF(2 ) offer high modu-
m
larity. However, their space complexities are considerably high in
comparison to other GF(2 ) multipliers, such as polynomial basis
m
235