Cryptography Reference
In-Depth Information
Algorithmus 6.1 E
zienter Algorithmus zur Exponentiation in Gruppen
Exponentiation(
G, g, n
)
Vorbedingung:
G
Gruppe,
g ∈ G
,
n ∈
N
mit Binärdarstellung
(
n
)
2
=
b
(0)
b
(1)
...b
(
l
)
}
+
,wobei
∈{
0
,
1
l
=max(
log
n,
0)
.
1.
Initialisierung.
i
=
l
;
h
=1
;
k
=
g
2.
Iteriertes Quadrieren.
solange
i ≥
0
falls
b
(
i
)=1
h
=
kh
k
=
k
2
i
=
i −
1
3.
Ergebnis ausgeben.
Gib
h
zurück.
Nachbedingung:
h
=
g
n
.
Algorithmus 6.2 E
zienter Algorithmus für den Erzeugertest in einer Gruppe bei ge-
gebenen Primfaktoren der Gruppenordnung
Erzeugertest(
G, g, n, P
)
Vorbedingung:
G
endliche Gruppe,
g ∈ G
,
n
=
|G|
,
P
= Menge der Primteiler von
|G|
.
für
p ∈ P
h
= Exponentiation(
G, g, n/p
)
falls
h
=1
terminiere und gib »
g
ist kein Erzeuger von
G
« zurück
gib »
g
ist Erzeuger von
G
« zurück
Zunächst nehmen wir an, dass
g
ein Erzeuger von
G
ist. Dann gilt
o
(
g
)=
n
und es
gilt
g
m
=1
für alle
m<n
. Deshalb terminiert der Algorithmus nicht frühzeitig, sondern
hält mit der korrekten Ausgabe »
g
ist Erzeuger von
G
«.
Es sei nun
g
kein Erzeuger von
G
und
m
=
o
(
g
)
. Dann gilt
m<n
und
m
n
aufgrund
von Satz 6.3.3. Insbesondere gibt es eine Primzahl
p ∈ P
, für die
p | n/m
gilt. Für eine
solche Primzahl erhalten wir dann
m
|
a
=
n/p
.
Dann gilt aber auch
g
n/p
=
g
m·a
=(
g
m
)
a
=1
a
=1
. Es gibt also eine Primzahl
p
|
n/p
, das heißt, es gibt eine Zahl
a
mit
m
·
∈
P
,
für die der Algorithmus mit »
g
ist kein Erzeuger von
G
« terminiert.
Quadratische Reste
Es sei
n>
0
.EineZahl
a
∈
Z
heißt
quadratischer Rest modulo
n
, wenn ggT
(
a, n
)=1
gibt mit
b
2
mod
n
=
a
mod
n
.Esseibemerkt,dassdamit
gilt und es ein
b
∈
Z
∈
Z
n
folgt (siehe Aufgabe 6.7.3). Mit anderen Worten:
a
ist ein quadratischer
Rest modulo
n
, falls
(
a
mod
n
)
zu
(
b
mod
n
)
Z
n
eine Wurzel hat. Ist
a
kein
quadratischer Rest modulo
n
und gilt trotzdem ggT
(
a, n
)=1
,also
(
a
mod
n
)
∈
Z
n
,dann
heißt
a
quadratischer Nichtrest modulo
n
. Die Menge aller quadratischen Reste modulo
Z
n
gehört und in
