Cryptography Reference
In-Depth Information
sociative and commutative since it follows regular multiplication rules (Conditions
2 and 5, respectively). The neutral element is 1 (Condition 3), and for every element
a
H
there exists an inverse
a
−
1
H
which is also an element of
H
(Condition 4).
This can be seen from the fact that every row and every column of the table contains
the identity element. Thus,
H
is a subgroup of
∈
∈
Z
11
(depicted in Figure 8.1).
Z
11
Fig. 8.1
Subgroup
H
of the cyclic group
G
=
More precisely, it is a subgroup of prime order 5. It should also be noted that 3 is
not the only generator of
H
but also 4, 5 and 9, which follows from Theorem 8.2.4.
An important special case are subgroups of prime order. If this group cardinality
is denoted by
q
, all non-one elements have order
q
according to Theorem 8.2.4.
From the Cyclic Subgroup Theorem we know that each element
a
G
of a group
G
generates some subgroup
H
. By using Theorem 8.2.3, the following theorem
follows.
∈
Theorem 8.2.6
Lagrange's theorem
Let H be a subgroup of G. Then
|
H
|
divides
|
G
|
.
Let us now consider an application of Lagrange's theorem:
Z
11
has cardinality
|
Z
11
|
Example 8.9.
The cyclic group
= 10 = 1
·
2
·
5. Thus, it
Z
11
have cardinalities 1, 2, 5 and 10 since these are
all possible divisors of 10. All subgroups
H
of
follows that the subgroups of
Z
11
and their generators
α
are given
below:
subgroup
elements
primitive elements
H
1
{
1
}
α
= 1
H
2
{
1
,
10
}
α
= 10
H
3
{
1
,
3
,
4
,
5
,
9
}
α
= 3
,
4
,
5
,
9
The following final theorem of this section fully characterizes the subgroups of
a finite cyclic group:
