Cryptography Reference
In-Depth Information
Berechne
(
x
1
,
α
1
,
β
1
)
und
(
x
2
,
α
2
,
β
2
)
.
Falls
x
2
=
x
1
, Stop!, sonst:
Berechne
(
x
2
,
α
2
,
β
2
)
und
(
x
4
,
α
4
,
β
4
)
.
Falls
x
4
=
x
2
, Stop!, sonst:
Berechne
(
x
3
,
α
3
,
β
3
)
und
(
x
6
,
α
6
,
β
6
)
.
Falls
x
6
=
x
3
, Stop!, sonst:
Berechne
(
x
4
,
α
4
,
β
4
)
und
(
x
8
,
α
8
,
β
8
)
usw.
=
Da
G
endlich ist, gibt es nach Lemma 10.2 einen Index
i
mit
x
2
i
x
i
, der Algorith-
mus bricht somit ab. Wie im obigen Schritt 2 erhalten wir hieraus die gesuchten
Zahlen
s
und
t
:
s
:
=
α
i
−
α
2
i
und
t
:
=
β
2
i
−
β
i
.
Der Speicherbedarf wird durch die Modifikation sehr gering. Die gespeicherten
Tripel
(
x
i
,
α
i
,
β
i
)
und
(
x
2
i
,
α
2
i
,
β
2
i
)
werden im Fall
x
2
i
=
x
i
durch die Tripel
(
)
(
)
x
i
+
1
,
α
i
+
1
,
β
i
+
1
und
x
2
i
+
2
,
α
2
i
+
2
,
β
2
i
+
2
überschrieben.
Beispiel
Wir betrachten erneut das Beispiel von Seite 183
:
Es sei
G
=
Z
13
=
2
.Wir
berechnen den diskreten Logarithmus
x
von
a
=
9 zur Basis 2 mit dem modifi-
zierten 2. Schritt.
1. Schritt:
Wir wählen erneut
G
1
:
=
{
1, 4, 7, 10
}
,
G
2
:
=
{
2, 5, 8, 11
}
,
G
3
:
=
{
3, 6, 9, 12
}
.
2. Schritt:
Wir bestimmen nun die Folgenglieder
x
1
,...,
x
i
wie oben beschrieben:
i
(
x
i
,
α
i
,
β
i
)
(
x
2
i
,
α
2
i
,
β
2
i
)
1
(
9, 1, 0
)
(
5, 1, 1
)
(
)
(
)
2
5,
1, 1
11
, 2, 3
3
(
12, 2, 2
)
(
10, 5, 6
)
(
)
(
)
4
11, 2, 3
11, 6, 7
Mit den Größen
=
=
=
=
=
=
i
4,
j
8,
α
i
2,
α
j
6,
β
i
3,
β
j
7
=
−
=
=
erhalten wir
s
4 (bzw.
s
8) und
t
4. Nun erhält man wie im Beispiel auf
Seite 183 den diskreten Logarithmus
x
=
8.
