Cryptography Reference
In-Depth Information
n
a
k
Beweis.
Wir setzen
d
:
=
ggT
(
n
,
k
)
und
t
:
=
o
(
)
und zeigen
t
=
d
. Es gilt:
n
d
k
d
a
k
a
n
(
)
=(
)
=
1,
d
und
d
natürliche Zahlen sind. Wegen der Aussage (iii) in
Lemma 6.1 (b) folgt hieraus
t
k
man beachte, dass
n
d
.
Zu
d
gibt es nach dem euklidischen Algorithmus, siehe Satz 4.10, Zahlen
r
,
s
|
∈
Z
r
d
+
s
d
. Damit erhalten wir für
t
die Darstellung:
=
+
=
mit
d
rn
sk
,d.h.1
tr
n
ts
k
t
=
d
+
d
.
n
d
ein Teiler des zweiten Summanden
ts
d
Wenn wir zeigen können, dass
ist, so
können wir aus obiger Darstellung von
t
folgern, dass
d
die Zahl
t
teilt.
Es gilt
a
kt
a
k
t
=(
)
=
1. Mit der Aussage (iii) in Lemma 6.1 (b) folgt
o
(
a
)=
n
|
t
k
,
also gilt
d
d
, woraus die Behauptung folgt:
d
k
|
|
t
t
.
Beispiel
Die multiplikative Gruppe
Z
18
ist zyklisch, es gilt:
Z
18
=
=
{
}
5
1, 5, 7, 11, 13, 17
.
Wegen
5
0
1, 5
1
5, 5
2
7, 5
3
17 , 5
4
13 , 5
5
=
=
=
=
=
=
11
Z
18
aus
o
erhalten wir für die Ordnungen der Elemente von
(
5
)=
6:
6
6
6
(
)=
)
=
(
)=
)
=
(
)=
)
=
o
1
1,
o
5
6,
o
7
3,
ggT
(
6, 0
ggT
(
6, 1
ggT
(
6, 2
6
6
6
(
)=
)
=
(
)=
)
=
(
)=
)
=
o
11
6,
o
13
3,
o
17
2.
(
(
(
ggT
6, 5
ggT
6, 4
ggT
6, 3
Z
18
.
Insbesondere sind 5 und 11 die einzigen erzeugenden Elemente von
Für unsere Zwecke ist eine unmittelbare Folgerung aus Lemma 6.2 für die erzeu-
genden Elemente einer zyklischen Gruppe wesentlich:
Korollar 6.3
Ist G
=
a
eine zyklische Gruppe der endlichen Ordnung n, so gilt:
a
k
∈
Z
=
⇔
(
)=
(a) Für k
gilt G
ggT
n
,
k
1
.
ϕ
(
)
(b) Die Gruppe G besitzt genau
n
erzeugende Elemente - dabei bezeichnet
ϕ
die
Euler'sche
ϕ
-Funktion (siehe Abschnitt 4.3.4).
