Page 38 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 21

Properties 1.9
1. Tr(αβ+ ) = Tr( ) + Tr( ), forall , α β ∈ F.
α
β
2. Tr a( α = aTr( ), forall a E, α ∈ F.
α
∈
)
3. The trace is a linear transformation from F onto E, where F
and E are viewed as vector spaces over E.
4. Tr a() = ma, forall a E.
∈
5. Tr(α = Tr( ),α forall α ∈ F.
q
)
The important definition of duality is given in the following.
Definition 1 .27 Let E be a finite field and F a finite extension of E.
,
Then two bases {αα ... α } and { ,ββ ... β } of F over E are said
1 2 m 1 2 m
to be dual bases if
⎧1 , if i = j
Tr(αβ = ⎨ (1.7)
)
i j ⎩ , 0 if i ≠ j

where 1 ≤ i, j ≤ m.
Th ere exist many distinct bases of F over E, but there are two
types of bases particularly important. The first is a polynomial basis
2
,
1
{, , αα ... , α m− 1 }, made up of the powers of a defining elem ent α
of F over E, where α is often taken to be a primitive element of F. The
other type of important basis is a normal basis, defined by a suitable
element of F.
By an E-automorphism of F (or an automorphism of F over E) we
m
mean an automorphism of F = F m = GF(q ) th at fixes the elements of
q
E = F = GF(q). The set of the E-automorphisms of F is a group, named
q
the Galois group of F over E, generated by the Frobenius automo rphism
q
ϕ (α) = α , for α∈ F, and made up of the m distinct el ements G ,
0
G , . . . , G defined as follows:
1 m − 1
GF → F
:
i
(1.8)
α → α q i = α G , α ∈ F,
i
where G = G and G = G = G = (identity automorphism).
i
m
0
I
i
1
0
1
1
Then, a basis {β , β , . . . , β m − 1 } is a normal basis for F over E if β = αG i
i
1
0
−
2
q
q
,
for some element α∈ F. Therefore, the set {,αα α ... , α q m 1 , where
α is a suitable element of F, will be a normal basis if the m elements
are linearly independent and α will be the generator or normal element
of the normal basis.
Definition 1.28 Let F = F m and E = F . Then a basis of F ove r E of the
q
q
−
form {,αα q ,α ... α q m 1 } consisting of a suitable element α ∈ F and
2
q
its conjugates with respect to E, is called a normal basis of F over E.
= F be a root of the irreducible polynomial
Example 1.14 Let α∈F 3 8
2
f (x) = x + x + 1 ∈ F [x]. Then the basis {,αα 2 , α = α + α + } 1 is a
3
2
2
4
2