Cryptography Reference
In-Depth Information
k
such that
k ⊆ k
, in which case we
Let
k
be a field. An
extension
of
k
is any field
k
/
k
is a vector space over
write
k
. Then
k
. If this vector space has finite dimension then
k
/
k
:
k
over
the
degree
of
k
, denoted [
k
], is the vector space dimension of
k
.
∈ k
is
algebraic
over
An element
θ
k
if there is some polynomial
F
(
x
)
∈ k
[
x
] such
k
of
∈ k
is algebraic over
k
/
that
F
(
θ
)
=
0. An extension
k
is
algebraic
if every
θ
k
.If
k
k ⊆ k
⊆ k
then
k
/
k
/
k
are algebraic. Similarly, if
k
/
is algebraic and
k
and
k
is finite
k
:
k
:
k
][
k
:
then [
k
]
=
[
k
].
Lemma A.6.1
Let
k
be a field. Every finite extension of
k
is algebraic.
Proof
See Theorem 4 of Section II.3 of [
573
], Proposition V.1.1 of [
329
] or Theorem V.1.11
of [
271
].
k
is the smallest field that contains both of
The
compositum
of two fields
k
and
them. We define
k
(
θ
)
={
a
(
θ
)
/b
(
θ
):
a
(
x
)
,b
(
x
)
∈ k
[
x
]
,b
(
θ
)
=
0
}
for any element
θ
.This
is th
e s
mallest field that contains
k
and
θ
. For example,
θ
may be algebraic over
k
(e.g.,
(
√
−
k
1)) or transcendental (e.g.,
k
(
x
)). More generally,
k
(
θ
1
,...,θ
n
)
= k
(
θ
1
)(
θ
2
)
···
(
θ
n
)
k
/
is the field generated over
k
by
θ
1
,...,θ
n
. A field extension
k
is
finitely generated
if
k
= k
(
θ
1
,...,θ
n
)forsome
θ
1
,...,θ
n
∈ k
.
Theorem A.6.2
Let
k
be a field. Suppose K is field that is finitely generated as a ring over
k
. Then K is an algebraic extension of
k
.
Proof
See pages 31-33 of Fulton [
199
].
A
n
algebraic clo
s
ure
of a field
k
is a field
k
such that every non-constant polynomial
. For details see Section V.2 of [
329
]. We always assume that there is
a fixed algebra
ic
closure
of
k
[
x
] has a root in
k
in
k
/
k
a
n
d we assume that every algebraic extension
k
is chosen
k
⊂ k
such that
and that
k
= k
. Since the main case of interest is
k = F
q
, this assumption
is quite natural.
We recall the notions of separable and purely inseparable extensions (see Sections
V.4 and V.6 of Lang [
329
], Section V.6 of Hungerford [
271
] or Sections A.7 and A.8 of
Stichtenoth [
529
]). An element
α
, algebraic over a field
k
,is
separable
(respectively,
purely
k
insepar
ab
le
) if the minimal polynomial of
α
over
has distinct roots (respectively, one
root) in
k
. Hence,
α
is separable over
k
if its minimal polynomial has non-zero derivative.
If char(
k
)
=
p
then
α
is purely inseparable if the minimal polynomial of
α
is of the form
x
p
m
−
a
for some
a
∈ k
.
∈ k
. One can define the
norm
and
trace
of
α
in terms of the matrix representation of multiplication by
α
as a linear map on the vector
space
k
/
Let
k
be a finite extension of fields and let
α
k
/
k
/
k
(see Section A.14 of [
529
] or
Se
ction IV.2 of [
355
]). When
k
is separable,
k
→ k
k
:
an equivalent definition is to let
σ
i
:
be the
n
=
[
k
] distinct embeddings (i.e.,
=
i
=
1
σ
i
(
α
) and the
∈ k
is
N
k
/
k
(
α
)
injective field homomorphisms), then the norm of
α
=
i
=
1
σ
i
(
α
).
trace
is Tr
k
/
k
(
α
)
An element
x
∈
K
is
transcendental
over
k
if
x
is not algebraic over
k
. Unless there is
an implicit algebraic relation between
x
1
,...,x
n
we write
k
(
x
1
,...,x
n
) to mean the field
k
(
x
1
)(
x
2
)
···
(
x
n
) where each
x
i
is transcendental over
k
(
x
1
,...,x
i
−
1
).
Definition A.6.3
Let
K
be a finitely generated field extension of
k
.The
transcen-
dence degree
of
K/
k
, denoted trdeg(
K/
k
), is the smallest integer
n
such that there are
x
1
,...,x
n
∈
K
with
K
algebraic over
k
(
x
1
,...,x
n
) (by definition
x
i
is transcendental over
k
(
x
1
,...,x
i
−
1
)). Such a set
{
x
1
,...,x
n
}
is called a
transcendence basis
for
K/
k
.