Cryptography Reference
In-Depth Information
2
01
5
501
101
3
4
301
401
1
201
Z
7
, ·
Figure 3.2
The cyclic group
.
Subgroups
When we elaborate on groups and their basic properties, it is sometimes useful to
consider subgroups. The notion of a subgroup is formally introduced in Definition
3.12.
Definition 3.12 (Subgroup)
A subset
H
of a group
G
is a
subgroup
of
G
if it is
closed under the operation of
G
and also forms a group.
For example, the integers are a subgroup both of the rational and real numbers
(with respect to the addition operation). Furthermore,
{
0
,
2
,
4
}
is a subgroup of
Z
6
,
+
with regard to addition modulo 6, and
{
0
}
and
{
1
}
are (trivial) subgroups
of every additive and multiplicative group.
An important class of subgroups of a finite group are those generated by an
element
a
, denoted as
has
ord
(
a
) elements.
Furthermore, we need the notion of cosets as captured in Definitions 3.13-3.15.
a
:=
{
a
j
|
j
≥
0
}
. The subgroup
a
Definition 3.13 (Left coset)
Let
G
be a group and
H
⊆
G
be a subset of
G
. For all
a
∈
G
,thesets
a
∗
H
:=
{
a
∗
h
|
h
∈
H
}
are called
left cosets
of
H
.
Definition 3.14 (Right coset)
Let
G
be a group and
H
⊆
G
be a subset of
G
.For
all
a
∈
G
,thesets
H
∗
a
:=
{
a
∗
h
|
h
∈
H
}
are called
right cosets
of
H
.
Definition 3.15 (Coset)
Let
G
be a (commutative) group and
H
⊆
G
. For all
a
∈
G
,thesets
a
∗
H
and
H
∗
a
are equal and are called
cosets
of
H
.
