Cryptography Reference
In-Depth Information
operating
x
with
y
. The identity element of a multiplicative group is usually denoted
by 1 and the identity element of an additive group is denoted by 0. Moreover, in
an additive group, the inverse of an element
x
is called the
opposite
element of
x
(or also the
negative
of
x
) and is denoted by
−
x
. For generic groups, we will
always use multiplicative notation.
If
G
and
H
are groups, then a map
f
:
G
→
H
is called a
homomorphism
if
G
. Clearly, a homomorphism maps the identity
of
G
to the identity of
H
and the inverse of an element to the inverse of its image.
A bijective homomorphism is called an
isomorphism
. In this case, the inverse
f
−
1
f
(
xy
)
=
f
(
x
)
f
(
y
)
for all
x
,
y
∈
:
H
→
G
is also an isomorphism and
G
and
H
are said to be
isomorphic
, denoted
G
=
H
. This means that
G
and
H
are essentially the “same” group, in the sense that
they share the same algebraic properties.
The group
G
is finite when
G
is a finite set, and the number of elements of
G
,
denoted
|
G
|
, is called the
order
of the group
G
.A
subgroup
of the group
G
is a
subset
H
G
such that the operation of
G
induces by restriction a group structure
in
H
.If
G
is a finite group and
x
⊆
∈
G
, then the
order
of
x
is the smallest positive
integer
i
such that
x
i
1. The subgroup
generated by x
, i.e., the smallest subgroup
of
G
containing
x
, consists of the elements 1
=
x
2
x
i
−
1
, where
i
is the order
,
x
,
...,
of
x
. We will denote this subgroup by
x
and we say that
x
is a generator of
x
.
A finite group is called
cyclic
5
when it has a generator, i.e., an element
g
∈
G
such
that
G
, which happens if and only if the smallest subgroup of
G
containing
g
is
G
itself. As is easily seen, such groups are always abelian and, if
G
=
g
=
g
,the
order of the element
g
is equal to the order of the group
G
.
Examples 2.2
1. Every one-element set
with the obvious operation is a group (in which
x
is
the identity and its own inverse). This group is isomorphic to the subgroup
{
x
}
{
1
}
of
any group
G
.
2.
Z
is a group with ordinary addition of integers. It is an infinite abelian group and
is also cyclic in the sense that the smallest subgroup containing 1 (or
−
1) is
Z
itself but
is not a group under multiplication because the only elements that
have inverse with respect to this operation are 1 and
Z
−
1.
3.
R
are groups with ordinary addition but they are not groups with respect to
multiplication because 0 has no inverse. However,
and
C
R
∗
= R−{
C
∗
= C−{
}
are multiplicative groups. All these groups are abelian but none of them are cyclic.
4. If
X
is a set, then the set
S
0
}
and
0
(also denoted
S
X
) of all permutations of
X
is a
group under the composition of functions, called the
symmetric group on X
.
(
X
)
Exercise 2.9
Show that if
G
is a group and
H
a nonempty subset of
G
, then
H
is a
subgroup if and only if
xy
H
and
x
−
1
H
.If
H
is finite then the first condition suffices, i.e.,
H
is a subgroup if and only if
xy
∈
H
for every
x
,
y
∈
∈
H
for all
x
∈
∈
H
,
∈
for all
x
y
H
.
5
There are also infinite cyclic groups and they are all isomorphic to the additive group of the
integers
Z
but in this topic we shall be mainly interested in finite groups.
