Cryptography Reference
In-Depth Information
Der Algorithmus bestimmt die
ν
diskreten Logarithmen
x
0
,...,
x
1
in der Grup-
ν−
g
p
ν
−
1
pe
der Ordnung
p
und damit den gesuchten diskreten Logarithmus
x
in
der Gruppe
der Ordnung
p
ν
.
g
Beispiel
Wir betrachten in der Gruppe
Z
251
=
6
mit 250 Elementen die zyklische Unter-
6
2
5
3
Eleme
n
ten und bestimmen den diskreten
gruppe
G
=
=
36
m
it 125
=
=
=
Log
36
(
)
Logarithmus
x
von
a
4, d. h.
x
4
. Dazu schreiben wir
x
in der 5 -
adischen Darstellung als
x
2
5
2
mit
x
0
,
x
1
,
x
2
x
=
x
0
+
x
1
5
+
∈{
0, . . . , 4
}
.
Wir bestimmen nun die Zahlen
x
0
,
x
1
,
x
2
aus der Gleichung
36
x
0
+
x
1
5
+
x
2
5
2
36
x
=
=
4.
Wir bestimmen
x
0
: Potenziere die Gleichung 36
x
4 mit 5
2
=
=
25 und erhalte
219
x
0
36
25
4
25
x
0
=(
)
=
=
1.
Berechne den diskreten Logarithmus
x
0
=
Log
36
25
(
1
)=
0.
Wir bestimmen
x
1
: Potenziere die Gleichung 36
x
1
5
+
x
2
5
2
36
−
0
=
4
·
=
4 mit
5
1
=
5 und erhalte
36
25
x
1
4
5
=
=
20 .
Log
36
25
20
=
=
Berechne den diskreten Logarithmus
x
1
2. Damit ist
x
1
be-
stimmt.
Wir bestimmen
x
2
: Potenziere die Gleichung 36
x
2
5
2
36
−
0
−
2
·
5
=
·
=
4
149 mit
5
0
=
1 und erhalte
36
25
x
2
=
149 .
Log
36
25
149
Berechne den diskreten Logarithmus
x
2
=
=
4. Damit ist
x
2
bestimmt.
5
2
Wir erhalten somit für
x
=
Log
36
(
4
)=
0
+
2
·
5
+
4
·
=
110. Und tatsächlich
gilt 36
110
=
4.
10.4.3 Volle Reduktion
Wir fassen nun die beiden Reduktionen zusammen und erhalten die
volle Reduk-
tion
des diskreten Logarithmenproblems auf Gruppen von Primzahlordnung.
