Page 289 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 9

Operations over

m
GF (2 )—Other

Bases

olynomial and normal bases studied in Chaps. 7 and 8, respec-
tively, are the two most used bases for representation of the
m
Pfield elements over the binary field GF(2 ). However, there are
other bases that can be used for the efficient computation of arithme-
m
tic operations over GF(2 ).

9.1 Dual Bases
The definition of dual bases is based on the trace function and the
concept of duality [LN83]. The duality was already introduced in
Chap. 1, where the definition of trace function was also given. A non-
m
zero linear function h from GF(2 ) to GF(2) is a function such that for
all χ , δ∈ GF(2 ) and c ∈ GF(2), h( χ + δ) = h( χ ) + h(δ) and h(c⋅ χ ) = c⋅h( χ )
m
m
hold. The trace function is a linear function from GF(2 ) to GF(2) in
β
such a way that the trace of β ∈ GF(2 ) is defined to be Tr() =∑ m−1 β 2 i .
m
i=0
As shown in Chap. 1, two bases {λλ ,... ,λ } and {μμ ... ,μ }
,
,
,
0 1 m− 1 0 1 m− 1
are said to be dual to one another if the following condition is satis-
fied by the trace values of the basis elements [Ber82]:
⎧1 , if i = j
Tr(λμ = ⎨ (9.1)
)
i j ⎩ , 0 if i ≠ j

m
,
Let {λλ ... ,λ } be a basis of GF(2 ) and let {μμ ,... ,μ }
,
,
0 1 m− 1 0 1 m− 1
m
be its dual basis. Then a field element A ∈ GF(2 ) can be represented
in the dual basis by the following expansion [HTDR88]:
m − 1 m − 1
A = ∑ a μ i ∑ Tr Aλ μ( i ) i (9.2)
=
i
i=0 i=0
269