Page 37 - Hardware Implementation of Finite-Field Arithmetic

20 Cha pte r O n e

It must be noted that in Example 1.12 we may adjoin either the
root θ or the root 2θ + 2 of f, and the same field would be obtained.
This fact is covered as follows. Let α and β be two roots of the
polynomial f ∈ E[x] that is irreducible over E. Then E(α) and E(β)
are isomorphic under an isomorphism, mapping α to β and keeping
the elements of E fixed.

1.3.3 Roots of Irreducible Polynomials
As described previ ously, starting from the prime fields F , other finite
p
fields can be constructed by the process of root adjunction. If f ∈ F [x]
p
is an irreducible polynomial over F of degree n, then a finite field
p
n
with p elements can be obtained by adjoining a root of f to F .
p
Furthermore, for every prime p and every positive integer n there
exists a finite field with p elements and therefore we can speak of the
n
n
finite field (or the Galois field) with q = p elemen ts, or of the finite
field of order q. This field is denoted by F or GF (q), where q is a
q
power of the prime characteristic p of F .
q
Theorem 1.2 If f is an irreducible polynomial in Fx [] of degree m,
q
then f has a root α in F m . Furthermore, all the roots of f are simple and are
q 2 m 1
−
q
q
given by the m distinct elements αα α , ... α , q of F m .
,
,
q
Let F m be an extension of F and let α ∈ F m. Then the elements
q
q
q
α, α , α , . . . , α q m − 1 are called the conjugates of α with respect
q 2
q
to F , t hat are distinct if and only if the minimal polynomial of α over
q
F has degree m. It can also be proven that if α is a primitive element of F ,
q
q
then so are all its conjugates with respect to any subfield of F .
q

Example 1.13 Let α∈ F 4 = F be a root of f (x) = x + x + 1 ∈ F [x]. The
4
2 16 2
2
2
conjugates of α with respect to F are α, α , α = α + 1, and α = α + 1,
4
8
2
where each of them is a primitive element of F .
16
1.3.4 Bases of Finite Fields
Considering a finite exten sion F = F m of the finite field E = F as a
q q
vector space over E, then F has dimension m over E. Moreover, if
{α , α , . . . , α } is a basis of F over E, then each element α in F can be
1 2 m
uniquely represented by α = a α + a α + ... + a α , with a ∈ E for
1 1 2 2 m m i
1 ≤ i ≤ m.
Definition 1.26 If α ∈ F = F m and E = F , then the trace of α over E is
q
q
defined by
Tr()α = α α + ... + α q m−1 (1.6)
+
q

It must be noted that the trace of α over E is the sum of the conjugates
of α with respect to E. Furthermore, Tr (α) is an element of E.
Let F = F m and E = F . Then the trace function satisfies the
q
q
following properties: