Page 36 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 19

EM) = E( , ... ,θ n ). If M consists of a single element θ ∈ F, then
θ
(
1
θ
=
LE() is said to be a simple extension of E and θ is a defining element
of L over E.
Definition 1.23 Let E be a subfield of F and θ ∈ F. If θ satisfies a
nontrivial polynomial equation with coefficients in E, that is, if
θ
a + a + ... + a θ n = 0 with a ∈ E not all being 0, then θ is said to be
0 1 n i
algebraic over E. An extension L of E is called an algebraic extension of
E if every element of L is algebraic over E.
Definition 1.24 If θ ∈ F is algebraic over E, then the uniquely
determined monic polynomial f ∈ E[x] generating the ideal
∈
θ
[
J = { g E x]: g( ) = } of E[x] is called the minimal (or irreducible, or
0
defining) polynomial of θ over E. The degree of θ over E means the
degree of f.
An extension field L of E may be viewed as a vector space over E. L
forms an abelian group under addition. Furthermore, each “vector” α
in L can be multiplied by a “scalar” k in E so that kα is in L and the
laws for multiplication by scalars are satisfied: (k + r)α = kα + rα,
k(α + β) = kα + kβ, (kr)α = k(rα) and 1α = α, where α, β ∈ L and k, r ∈ E
[LN94].
Definition 1.25 Let L be an extension field of E. If L, considered as a
vector space over E, is finite-dimensional, then L is called a finite
extension of E. The dimension of the vector space L over E is called the
degree of L o ver E, and it is represented as [L:E].
Given a simple extension E(θ ) of E obtained by adjoining an
algebraic element θ, it can be observed that if F is an extension of E
and if θ ∈ F is algebraic over E, then E(θ) is an algebraic and finite
extension of E. Furthermore, E(θ) is isomorphic to E[x]/f if θ ∈ F is
algebraic of degree n over E and f is the minimal polynomial of θ over
E. It can also be proven that the elements of the simple algebraic
extension E(θ) of E are polynomial expressions in θ, and that any
element of E(θ) can be uniquely represented in the form a + a θ + . . . +
0
1
n−1
2
n−1
a θ with a ∈ E for 0 ≤ i ≤ n – 1, where n= [E(θ):E] and {1, θ, θ , . . . , θ }
n i
is a basis of E(θ) over E.
Theorem 1.1 Let f ∈ E[x] be irreducible over the field E. Then there
exists a simple algebraic extension of E with a root of f as a defining
element.
Following is an example of root adjunction.
2
Example 1.12 Let f (x) = x + x + 2 ∈ F [x], which is irreducible over F ,
3 3
and let θ be a root of f. It can be proven that the other root of f in L =
2
2
F [x]/f is 2θ + 2, since f (2θ + 2) = (2θ + 2) + (2θ + 2) + 2 = θ + θ + 2 = 0.
3
Therefore, the simple algebraic extension L = F (θ) consists of the
3
following nine elements: {, , , ,01 2 θθ + , 1 θ + , 2 2 2θ + , 1 2θ + 2 }.
θ
,