Cryptography Reference
In-Depth Information
Der Vollständigkeit halber sei auch der folgende Satz erwähnt.
Z
n
genau dann zyklisch, wen
n
Satz 6.3.5 (Einheitengruppen).
Es sei
n ≥
2
.Dannist
n
=2
,
n
=4
,
n
=
p
r
p
r
für eine Primzahl
p>
2
und ein
r
oder
n
=2
·
≥
1
gilt.
Ein Element
a ∈
Z
n
heißt
primitives Element modulo
n
, wenn es ein Erzeuger von
Z
n
ist. Der letzte Satz ist also ein hinreichendes und notwendiges Kriterium dafür, ob es
primitive Elemente modulo einer Zahl
n
gibt.
Schnelle Exponentiation und Erzeugertests
Häufig möchte man Potenzen eines gegebenen Gruppenelementes schnell berechnen: Bei
gegebenem
g
0
möchte man also
g
n
berechnen. Für große Zahlen
n
ist
der naive Ansatz, nämlich
gn
-mal zu multiplizieren, völlig unpraktikabel, da er
n−
1
Multiplikationen benötigen würde. Glücklicherweise kommt man mit deutlich weniger
Multiplikationen aus. Dabei benutzt man die Idee des
iterierten Quadrierens
.Umzum
Beispiel
g
2
500
zu berechnen, rechnet man einfach:
∈
G
und
n
≥
2
g
2
2
···
···
,
500-mal quadrieren
was lediglich 500 (statt
2
500
−
1
) Multiplikationen benötigt, also
log(2
500
)
viele. Diese
Idee kann man leicht auf Zahlen
n
erweitern, die keine Zweierpotenzen sind: Betrachten
wir dazu (die kleine Zahl)
n
=11
als Beispiel. Wir wollen also
g
11
berechnen. Es ist
11 = 2
3
+2
1
+2
0
, also in Binärdarstellung
(11)
2
= 1011
.Mit
b
= (11)
2
erhalten wir
g
11
=
g
2
3
· g
2
0
=
i
=0
g
b
(3
−i
)
·
2
i
, wobei, wie üblich,
b
=
b
(0)
b
(1)
b
(2)
b
(3)
ist. Um nun
g
11
zu berechnen, könnte man also zunächst
g
i
=
g
2
i
durch
i
-faches iteriertes Quadrieren für
alle
i
mit
0
≤ i ≤
3
berechnen und erhält dann mit
g
0
·
· g
2
1
g
3
das gewünschte Ergebnis
g
11
.
Noch ezienter ist die Berechung allerdings, wenn man Ergebnisse bereits durchgeführter
Quadrierungen wiederverwendet, denn
g
i
erhält man durch
eine
Quadrierung gemäß
g
i
=
(
g
i−
1
)
2
. Diese Idee ist in Algorithmus 6.1 umgesetzt, wobei
g
1
·
·
dieuntereGaußklammer
bezeichnet; für eine reelle Zahl
r
ist also
r
=max
{
i
∈
Z
|
i
≤
r
}
. Offensichtlich gilt:
Satz 6.3.6 (schnelle Exponentiation).
Für eine Gruppe
G
führt Algorithmus 6.1, gegebe
n
g
0
,
O
(log
n
)
Multiplikationen in
G
zur Berechnung von
g
n
aus.
∈
G
und
n
≥
Kennt man die Ordnung einer (zyklischen) Gruppe und alle ihre Primteiler, so lässt
sich leicht feststellen, ob ein gegebenes Element ein Erzeuger der Gruppe ist. Ein entspre-
chendes Verfahren ist Algorithmus 6.2.
Satz 6.3.7 (schneller Erzeugertest).
Für eine endliche Gruppe
G
mit Ordnung
n
führt
Algorithmus 6.2
O
((log
n
)
2
)
Multiplikationen in
G
aus, um festzustellen, ob ein gegebenes
Element aus
G
Erzeuger von
G
ist.
Beweis.
Die obere Schranke für die Komplexität des Algorithmus ergibt sich direkt aus
Satz 6.3.6 und der Tatsache, dass jede Zahl
n
nicht mehr als
log
n
Primfaktoren hat. Um
die Korrekheit zu zeigen, sei
n
=
|G|
und
g ∈ G
ein beliebiges Element.
