Cryptography Reference
In-Depth Information
Satz 6.3.2 (kleiner Satz von Fermat).
Es sei
G
eine endliche Gruppe der Ordnung
n
.
Dann gilt
g
n
=1
für alle
g ∈ G
.
Lemma 6.3.1 (Untergruppen endlicher Gruppen).
Es sei
G
eine endliche Gruppe und
U ⊆ G
.Dannist
U
eine Untergruppe von
G
, genau dann, wenn
1
∈ U
und
a · b ∈ U
für
alle
a, b
∈
U
gilt.
Beweis.
Es seien
G
und
U
wie in der Aussage des Lemmas gegeben. Es bleibt nur zu
zeigen, dass
a
−
1
∈ U
für alle
a ∈ U
gilt, d. h., dass zu jedem Element aus
U
auch sein
Inverses in
U
enthalten ist. Dies folgt aber leicht aus dem kleinen Satz von Fermat: Es sei
a ∈ U
. Nach dem kleinen Satz von Fermat gilt
a
|G|
=1
und damit
a
|G|−
1
·
a
|G|−
1
=
a
=
a
·
1
. Folglich ist
a
−
1
=
a
|G|−
1
∈
U
.
Satz 6.3.3 (Satz von Lagrange).
Es sei
G
eine endliche Gruppe und
U
eine Untergrup
pe
von
G
.Danngilt
|
U
|||
G
|
.
Folgerung 6.3.2.
Ist
G
eine endliche Gruppe und
U
eine echte Untergruppe von
G
,
so
gilt
|
U
|≤|
G
|
/
2
.
Es sei
G
eine Gruppe und
g
∈
G
.Das
Erzeugnis von
g
in
G
,dasmit
g
bezeichnet wird,
ist die Menge
{
1
,g,g
−
1
,g
2
,g
−
2
,...}
. Sie bildet eine Untergruppe von
G
. Die Mächtigkeit
von
wird
Ordnung von
g
genannt und mit
o
(
g
)
bezeichnet. Falls
o
(
g
)
endlich ist, dann
gilt
g
=
{
1
,g,g
2
,...,g
o
(
g
)
−
1
}
g
. Alle diese Elemente sind verschieden und es gilt
g
o
(
g
)
=1
nach dem kleinen Satz von Fermat. Des Weiteren gilt für jedes
m
∈
Z
:
g
m
=
g
m
mod
o
(
g
)
.
(6.3.1)
Insbesondere gilt
g
m
=1
genau dann, wenn
o
(
g
)
|
m
.
Eine Gruppe
G
heißt
zyklisch
,wenn
G
=
g
für ein
g ∈ G
gilt. Aus Satz 6.3.3 mit
U
=
g
,für
g
∈
G, g
=1
, erhalten wir direkt:
Lemma 6.3.2.
Jede Gruppe von Primzahlordnung ist zyklisch.
Lemma 6.3.3 (zyklische Gruppen).
1. Jede zyklische Gruppe ist isomorph zu
Z
n
mit
mit Addition (siehe auch Aufgabe 6.7.18); insbe-
sondere ist jede zyklische Gruppe kommutativ.
2. Es sei
G
eine endliche zyklische Gruppe der Ordnung
n
mit Erzeuger
g
.
a. Zu jedem Teiler
m
von
n
gibt es genau eine Untergruppe
U
von
G
mit Ordnung
m
,nämlich
Addition für ein
n>
0
oder zu
Z
g
n/m
. Diese Untergruppen sind offensichtlich zyklisch und wegen
Satz 6.3.3 besitzt
G
keine weiteren Untergruppen.
b. Für jedes
i ∈
N
gilt
o
(
g
i
)=
n/
ggT
(
i, n
)
.
r
←
G
,d.h.,
X
G
ist eine Zufallsvariable, die ein
Element aus
G
zufällig gleichverteilt liefert (vgl. auch die Notation in Abschnitt 3.3).
Insbesondere gilt
Prob
Für eine endliche Gruppe
G
sei
X
G
G
.
Über die Anzahl der Erzeuger einer zyklischen Gruppe folgt aus Lemma 6.3.3:
{
X
G
=
g
}
=1
/
|
G
|
für alle
g
∈
Folgerung 6.3.3.
Es sei
G
eine zyklische Gruppe der Ordnung
n
.
