Cryptography Reference
In-Depth Information
Dabei heißt eine nichtleere Teilmenge
U
von
G
bekanntlich
Untergruppe
, wenn
für alle
a
,
b
U
gilt
ab
−
1
∈
∈
U
.
Beispiel
Die ad
di
tiven Gruppen
(
Z
,
+)
und
(
Z
n
,
+)
sind zyklisch, es gilt
Z
=
1
und
Z
n
=
1
. Beachte, dass hier 0 und 0 die neutralen Elemente sind.
Z
8
=
{
ist nicht zyklisch, da
a
2
Die multiplikative Gruppe
1, 3, 5, 7
}
=
1 für
∈
Z
8
jedes Element
a
gilt.
Z
p
zyklisch (das wird in
Satz 6.12 bewiesen). Diese Tatsache ist für viele Kryptosysteme grundlegend.
Für jede Primzahl
p
ist die multiplikative Gruppe
Z
p
ν
zyklisch (das wird in Satz
Für jede ungerade Primzahl und jedes
ν
∈
N
ist
6.14 bewiesen).
(
·
)
Für jedes Element
a
einer Gruppe
wird die Mächtigkeit der von
a
erzeugten
Untergruppe die
Ordnung
von
a
in
G
genannt, in Zeichen:
G
,
o
(
a
)
:
=
|
a
|
,
wobei
o
unendlich ist. Das folgende Ergebnis ist
aus der linearen Algebra bekannt. Man vgl. auch die Aufgabe 6.1.
(
a
)
:
=
∞
gesetzt wird, falls
a
Lemma 6.1
Es sei a ein Element einer Gruppe G.
j stets a
i
a
j
.
=
=
(a) Wenn a unendliche Ordnung hat, so folgt aus i
(b) Wenn a endliche Ordnung n hat, d. h. o
(
a
)=
n
∈
N
, so ist n die kleinste natürli-
che Zahl mit a
n
=
∈
Z
1
, und es gilt für s
,
t
:
1,
a
,
a
2
,...,
a
n
−
1
(
i
)
a
=
{
}
,
a
s
a
t
(
ii
)
=
⇔
o
(
a
)
|
s
−
t,
a
s
(
iii
)
=
1
⇔
o
(
a
)
|
s.
Wir werden diese Tatsachen im Folgenden häufig benutzen. Vor allem die Aus-
sage in (iii) sollte man sich gut einprägen.
Ist die Ordnung eines Gruppenelements
a
∈
G
endlich, so kann man die Ordnun-
gen der Potenzen von
a
nach einer einfachen Formel bestimmen, es gilt nämlich:
Lemma 6.2
Ist a ein Element der endlichen Ordnung n einer Gruppe G, so gilt für jedes k
∈
Z
n
a
k
(
)=
o
.
(
)
ggT
n
,
k
