Cryptography Reference
In-Depth Information
1. Die Anzahl der Erzeuger von
G
ist
φ
(
n
)
,wobei
φ
die Eulersche
φ
-Funktion bezeich-
net.
2. Für die Wahrscheinlichkeit
Prob
{
X
G
=
G
}
, dass ein zufällig gewähltes Element
aus
G
ein Erzeuger von
G
ist, gilt:
1
1+log
n
Prob
{
X
G
=
G
}≥
.
(6.3.2)
Beweis.
Der erste Teil folgt direkt aus Lemma 6.3.3, Unterpunkt 2.b.
Es sei
n
=
p
α
0
···p
α
r−
1
die Primfaktorzerlegung von
n
(wie in Satz 3.5.1), ohne Ein-
r−
1
schränkung mit
p
0
<p
1
<
···
<p
r−
1
. Dann gilt:
=
φ
(
n
)
n
(1
=
(
p
0
−
Prob
{
X
G
=
G
}
1)
p
α
r−
1
−
1
r−
1
1)
p
α
0
−
1
0
···
(
p
r−
1
−
p
α
r−
1
r−
1
p
α
0
···
(2
=
p
0
−
1
p
r−
1
−
1
···
p
0
p
r−
1
(3)
≥
1
2
·
2
3
···
r
r
+1
1
1+
r
(4
=
.
Dabei ergibt sich (
1
) aus Satz 3.5.1, durch Kürzen gelangen wir zu (
2
), hinter (
3
)steckt
die Überlegung, dass
p
i
>i
+1
gilt, und (
4
) erhalten wir wieder durch Kürzen. Da je
de
Primzahl
≥
2
ist, gilt
r
≤
log
n
. Daraus folgt die Behauptung.
Die Wahrscheinlichkeit, dass ein zufällig gewähltes Element aus
G
ein Erzeuger von
G
ist, ist also recht hoch. Konkreter erhalten wir etwa für eine zyklische Gruppe
G
mit
höchstens
2
1024
Elementen, und damit
log(
|G|
)
≤
1024
, folgende Aussage: Wenn man
mindestens 711 Mal ein Element aus
G
zufällig wählt, dann ist die Wahrscheinlichkeit
dafür, dass unter diesen Elementen ein Erzeuger von
G
ist, mindestens
1
−
(1
−
1
/
1025)
711
und damit
≥
2
. Es sei bemerkt, dass die Abschätzung (6.3.2) recht grob ist. Häufig wird
die Wahrscheinlichkeit, einen Erzeuger zu finden, sogar deutlich höher sein als diejenige,
die man aus (6.3.2) ableiten kann; zum Beispiel ist sie für Gruppen von Primzahlordnung
fast eins, da, wie wir wissen, jedes Element in einer solchen Gruppe, abgesehen vom
Einselement, ein Erzeuger ist.
Eine mögliche Strategie, einen Erzeuger einer (beliebigen) endlichen zyklischen Gruppe
zu finden, ist also, solange zufällig ein Element der Gruppe zu wählen, bis man einen
Erzeuger gefunden hat. Dabei stellt sich natürlich die Frage, wie man feststellt, ob ein
Gruppenelement ein Erzeuger ist. Dieser Frage gehen wir im Folgenden nach. Zunächst
betrachten wir noch wichtige Beispiele für zyklische Gruppen:
Z
p
eine zyklische Gruppe.
Satz 6.3.4.
Es sei
p
eine Primzahl. Dann ist
