Cryptography Reference
In-Depth Information
Korollar 6.10
(Kleiner Satz von Fermat)
Es sei p eine Primzahl. Für alle a
gilt a
p
∈
Z
≡
(
)
a
mod
p
.
Z
p
der Ordnung
p
Beweis.
Ist
a
=
0, so liegt
a
in der multiplikativen Gruppe
−
1.
≡
(
−
)
D
ie
B
ehauptung folgt dann aus Korollar 6.9 (b) wegen
p
1
mod
p
1
. F
ür
a
=
0 ist die Aussage unmittelbar klar.
Z
p
6.1.7 Die Gruppen
sind zyklisch
Z
p
ν
,
p
eine Primzahl und
Die Gruppen
ν
∈
N
, sind in der Kryptologie wichtig,
Z
p
ν
=
Z
p
, so handelt es sich um die
multiplikative Gruppe des endlichen Körpers
besonderes im Fall
ν
=
1. Ist
ν
=
1, d. h.
Z
p
Z
p
. Wir zeigen nun, dass
für
jede Primzahl
p
eine zyklische Gruppe ist.
Wir betrachten vorab eine beliebige endliche abelsche Gruppe
G
und nennen
ε
(
)
=
{
(
)
∈
}
G
:
kgV
o
a
;
a
G
den
Exponenten
von
G
.
Nach dem Satz 6.4 von Lagrange gilt
ε
(
)
| |
|
G
G
. Wir können sogar zeigen:
Lemma 6.11
In einer endlichen abelschen Gruppe G gibt es ein Element b mit o
(
b
)=
ε
(
G
)
.
ε
(
)=
···
Beweis.
Es sei
G
m
1
m
r
eine Zerlegung in teilerfremde Primzahlpotenzen
ε
(
)
das kleinste gemeinsame Vielfache aller Elementordnungen
ist, existiert zu jedem
m
i
m
1
,...,
m
r
.Da
G
ein
a
i
∈
G
mit
o
(
a
i
)=
m
i
k
i
für ein
k
i
∈
N
. Nach
a
k
i
i
(
)=
Lemma 6.2 gilt dann
o
m
i
. Wegen Aufgabe 6.2 gilt somit für das Element
a
k
1
a
k
r
G
wegen der Teilerfremdheit der Ordnungen der Elemente
a
k
i
i
=
···
∈
b
:
r
r
i
=
1
o
(
a
k
i
(
)=
)=
···
o
b
m
1
m
r
.
i
(
)=
ε
(
)
Für das Element
b
gilt daher
o
b
G
.
Mit diesem Lemma folgt, dass eine endliche abelsche Gruppe genau dann zy-
klisch ist, wenn
ε
(
G
)=
|
G
|
erfüllt ist. Damit können wir nun den folgenden
wichtigen Satz begründen:
Satz 6.12
Jede endliche Untergruppe G der multiplikativen Gruppe K
×
eines Körpers K ist zyklisch.
Insbesondere ist für jede Primzahl p die Gruppe
Z
p
zyklisch.
