Cryptography Reference
In-Depth Information
Theorem 8.2.4
Let G be a finite cyclic group. Then it holds that
1. The number of primitive elements of G is
Φ
(
|
G
|
)
.
2. If
|
G
|
is prime, then all elements a
= 1
∈
G are primitive.
The first property can be verified by the example above. Since
Φ
(10)=(5
−
1)(2
1)=4, the number of primitive elements is four, which are the elements 2,
6, 7 and 8. The second property follows from the previous theorem. If the group
cardinality is prime, the only possible element orders are 1 and the cardinality itself.
Since only the element 1 can have an order of one, all other elements have order
p
.
−
8.2.3 Subgroups
In this section we consider subsets of (cyclic) groups which are groups themselves.
Such sets are referred to as
subgroups
. In order to check whether a subset
H
of a
group
G
is a subgroup, one can verify if all the properties of our group definition in
Section 8.2.1 also hold for
H
. In the case of cyclic groups, there is an easy way to
generate subgroups which follows from this theorem:
Theorem 8.2.5
Cyclic Subgroup Theorem
Let
(
G
,
G with
ord
(
a
)=
s is the primitive element of a cyclic subgroup with s ele-
ments.
◦
)
be a cyclic group. Then every element a
∈
This theorem tells us that any element of a cyclic group is the generator of a sub-
group which in turn is also cyclic.
Example 8.8.
Let us verify the above theorem by considering a subgroup of
G
=
Z
11
. In an earlier example we saw that ord(3)=5, and the powers of 3 generate the
subset
H
=
according to Theorem 8.2.5. We verify now whether this
set is actually a group by having a look at its multiplication table:
{
1
,
3
,
4
,
5
,
9
}
Table 8.2
Multiplication table for the subgroup
H
=
{
1
,
3
,
4
,
5
,
9
}
×
mod 11
13459
1
13459
3
39145
4
41593
5
54931
9
95314
H
is closed under multiplication modulo 11 (Condition 1) since the table only
consists of integers which are elements of
H
. The group operation is obviously as-
