Cryptography Reference
In-Depth Information
:
→
Proposition 2.7
Let G be a group and f
G
H a homomorphism. Then f
f
:
/
→
induces an isomorphism
G
Ker
f
Im
f.
f
f
Proof
Let
K
=
Ker
f
. We define a map
:
G
/
K
→
Im
f
by
(
Kx
)
=
f
(
x
)
∈
Ky
, then
xy
−
1
Im
f
, for every
x
∈
G
.
f
is well-defined because if
Kx
=
∈
K
and so
)
−
1
xy
−
1
f
(
x
)
f
(
y
=
f
(
)
=
1, and multiplying both sides of the equality by
f
(
y
)
we
f
is clearly a homomorphism and is surjective.
obtain that
f
(
x
)
=
f
(
y
)
. Moreover,
f
On the other hand, Ker
={
Kx
∈
G
/
K
|
f
(
x
)
=
1
}={
Kx
∈
G
/
K
|
x
∈
K
}={
K
}
f
is the trivial subgroup (its unique element is the identity
K
of
G
and hence Ker
/
K
).
f
is indeed an isomorphism.
Thus we see that
Remark 2.2
Note that from Proposition 2.7 it follows that if
f
:
G
→
H
is a
homomorphism, then
(
G
:
Ker
f
)
=|
Im
f
|
. In particular, if
f
is surjective and
K
=
Ker
f
, then
(
G
:
K
)
=|
H
|
.
Next we recall the concept of ring. A
ring
is a set
R
with at least two elements
0
=
1 and two operations
+
,
·
, satisfying the following properties:
•
(
R
,
+
)
is an abelian group with identity element 0.
•
The multiplication is associative with identity element 1.
•
Distributive laws
. For all
x
,
y
,
z
∈
R
,
x
(
y
+
z
)
=
xy
+
xz
,
(
x
+
y
)
z
=
xz
+
yz
.
If the multiplication of the ring is, furthermore, commutative, then we say that
R
is a commutative ring. The multiplicative identity 1 is called the
identity
of the
ring (sometimes rings without identity are considered but all the rings that we will
consider are commutative and with 1). If
R
is a ring, an element
a
R
is a
unit
(or
an
invertible element
) if and only if it has a multiplicative inverse, i.e., there exists
an element
x
−
1
such that
xx
−
1
∈
1. It is immediate to see that the set
R
∗
of the units of
R
is a group with the multiplication induced by that of
R
(and with
identity 1). If
R
is a commutative ring, an element
x
x
−
1
x
=
=
∈
R
is called a
zero divisor
if
x
0. If
x
is a
zero divisor then
x
is not a unit of
R
(note that 0 is neither a unit nor a zero divisor).
A commutative ring without zero divisors is called an
integral domain
.
=
0 and there exists an element
y
∈
R
such that
y
=
0 and
xy
=
Examples 2.3
1.
Z
, with the usual addition and multiplication of integers, is a commutative ring.
The only units of
Z
∗
={−
Z
−
,
}⊆Z
are 1 and
1 (hence the group of units is
1
1
)
Z
and there are no zero divisors, so that
is an integral domain.
2.
R
are rings with ordinary addition and multiplication. All of their nonzero
elements are units (a property that, as we shall see below, characterizes the com-
mutative rings that are fields). In particular, these rings are integral domains.
and
C
The concepts of ring homomorphism and ring isomorphism are defined similarly
to those for groups, as follows:
Definition 2.19
Let
R
and
S
be rings and
f
S
a function.
f
is a
ring
homomorphism
in case it preserves the ring operations and the identity, namely:
:
R
→
