Cryptography Reference
In-Depth Information
Using the notion of a subfield, we can introduce the notion of a prime field.
This is suggested in Definition 3.19.
Definition 3.19 (Prime field)
A
prime field
is a field that contains no proper sub-
field.
For example,
Q
is a(n infinite) prime field, whereas
R
is not a prime field (note
that
). If we only consider finite fields, then a prime field
must contain a prime number of elements, meaning that it must have a prime order.
Q
is a proper subfield of
R
3.1.3
Homomorphisms and Isomorphisms
In algebraic discussions and analyses, one often uses the notion of a homomorphism
or isomorphism as formally introduced in Definitions 3.20 and 3.21.
Definition 3.20 (Homomorphism)
Let
A
and
B
be two algebraic structures. A
mapping
f
:
A
B
is called a homomorphism of
A
into
B
if it preserves the
operations of
A
.Thatis,if
→
◦
is an operation of
A
and
•
an operation of
B
,then
f
(
x
◦
y
)=
f
(
x
)
•
f
(
y
)
must hold for all
x, y
∈
A
.
Definition 3.21 (Isomorphism)
A homomorphism
f
:
A
B
is an
isomorphism
if it is injective (“one to one”). In this case, we say that
A
and
B
are
isomorphic
and we write
A
=
B
.
→
Another way of saying that two algebraic structures are isomorphic is to say
that they are structurally equivalent. Furthermore, if an isomorphism of an algebraic
structure onto itself is considered, then one frequently uses the term automorphism
as formally introduced in Definition 3.22.
Definition 3.22 (Automorphism)
An isomorphism
f
:
A
→
A
is an
automor-
phism
.
Against this background, a
group homomorphism
is a mapping
f
between
two groups
S
1
,
∗
1
and
S
2
,
∗
2
such that the group operation is preserved (i.e.,
f
(
a
∗
1
b
)=
f
(
a
)
∗
2
f
(
b
) for all
a, b
∈
S
1
) and the identity element
e
1
of
S
1
,
∗
1
is mapped to the identity element
e
2
of
S
2
,
∗
2
(i.e.,
f
(
e
1
)=
e
2
). If
f
:
is injective (“one to one”), then the group homomorphism
is a group isomorphism (i.e.,
S
1
,
∗
1
→
S
2
,
∗
2
∗
1
=
).
It can be shown that every cyclic group with order
n
is isomorphic to
S
1
,
S
2
,
∗
2
Z
n
,
+
.
Hence, if we know
, then we know all structural properties of every cyclic
group of order
n
. Furthermore, it can be shown that
Z
n
,
+
Z
n
,
is cyclic if and only if
n
is a prime, a power of a prime
>
2, or twice the power of a prime
>
2 (see Definition
·
