Cryptography Reference
In-Depth Information
erhalten wir wegen
d
=
ggT
(
−
4, 12
)=
4 und da
v
=
2 eine Lösung der Kongru-
12
+
4
Z
=
+
Z
enzgleichung ist die Menge 2
2
3
. Folglich ist der diskrete Loga-
rithmus
x
=
Log
g
(
a
)
unter den Zahlen 2 , 5 , 8 , 11 zu suchen. Man testet:
2
2
4, 2
5
6, 2
8
=
=
=
9,
=
Log
g
(
)=
sodass
x
a
8 gilt.
10.3.2 Modifikation des zweiten Schrittes
Bei der beschriebenen Version von Pollards
-Methode sind im 2. Schritt für jedes
i
die Tripel
zu speichern. Wir geben nun eine Modifikation dieses 2.
Schrittes an, sodass fast kein Speicher benötigt wird. Dazu begründen wir vorab:
(
x
i
,
α
i
,
β
i
)
Lemma 10.2
Es seien X eine endliche Menge und f
:
X
→
X eine Abbildung. Für jede Folge
(
x
i
)
in
=
(
)
∈
N
=
X mit x
i
+
1
f
x
i
gibt es ein i
mit x
i
x
2
i
.
Beweis.
Es seien
x
1
,
x
2
,...,
x
v
,...,
x
v
+
p
−
1
verschieden, aber
x
v
+
p
=
x
v
. Dann gilt
∈
N
für alle
a
:
x
v
+
ap
=
x
v
.
Es folgt
x
j
+
ap
=
x
j
für alle
j
≥
v
. Wähle nun ein
i
≥
v
mit
p
|
i
, etwa
i
=
dp
.
Dann gilt
=
=
=
x
2
i
x
i
+
i
x
i
+
dp
x
i
.
Damit ist ein passendes
i
gefunden.
Bemerkung
Nach dem Beweis dieses Lemmas
kreisen
die Folgenglieder
x
i
nach einer evtl.
Vorperiode
x
1
,...,
x
v
mit der Periode
p
. Vergleiche diese
Veranschaulichung
mit
dem griechischen Buchstaben
.
Wir nutzen Lemma 10.2 um Schritt 2 zu modifizieren.
2. Schritt - modifiziert.
Wir bestimmen ganze Zahlen
s
,
t
mit
a
s
g
t
. Dazu er-
=
∈
a
α
i
g
β
i
;
β
i
∈
N
0
,
zeugen wir erneut die Folgenglieder
x
0
=
1,
x
1
,
x
2
,...
α
i
,
die durch folgende Vorschrift gegeben sind:
⎧
⎨
∈
ax
i
,
falls
x
i
G
1
x
i
x
i
+
1
:
=
,
falls
x
i
∈
G
2
.
⎩
∈
gx
i
,
falls
x
i
G
3
(
)
Nun speichern wir aber nicht alle Tripel
, sondern gehen wie folgt vor:
In jedem Schritt werden zwei Werte berechnet, nämlich
x
i
+
1
aus
x
i
und
x
2
i
+
2
aus
x
2
i
, ausführlicher:
x
i
,
α
i
,
β
i
