Cryptography Reference
In-Depth Information
10.3.1 Das Verfahren
Pollards
-Methode
besteht aus drei Schritten:
1. Schritt.
Zerlege die Menge
G
in drei (etwa gleich große) Teilmengen
G
1
,
G
2
,
G
3
mit 1
G
2
.
2. Schritt.
Bestimme ganze Zahlen
s
,
t
mit
a
s
∈
g
t
wie folgt: Erzeuge die Folge
=
x
0
=
1,
x
1
,
x
2
, . . . durch
⎧
⎨
ax
i
,
falls
x
i
∈
G
1
x
i
=
∈
x
i
+
1
:
,
falls
x
i
G
2
.
⎩
gx
i
,
falls
x
i
∈
G
3
a
2
,
ag
,
g
2
∈{
}
∈{
}
Offenbar gilt
x
1
a
,
g
,
x
2
, ..., d. h.
a
α
i
g
β
i
mit
x
i
=
α
i
,
β
i
∈
N
0
für alle
i
=
1, 2, . . . .
|
|
=
∈
N
<
=
Da
G
endlich ist,
G
n
, gibt es Indizes
i
,
j
,
i
j
mit
x
i
x
j
, und es gilt:
a
α
j
g
β
j
a
α
i
−α
j
g
β
j
−β
i
a
α
i
g
β
i
=
⇔
=
⇔
=
x
i
x
j
.
Damit haben die Zahlen
=
α
i
− α
j
und
t
:
=
β
j
− β
i
s
:
die gewünschte Eigenschaft.
Bemerkung
Im Allgemeinen kann man für
s
und
t
betragsmäßig kleinere Zahlen wählen.
Dazu reduziere man
α
i
−
α
j
und
β
j
−
β
i
modulo
n
, d. h. man teilt
α
i
−
α
j
und
− β
i
durch
n
mit Rest und erhält:
β
j
α
i
−
α
j
=
q
s
n
+
s
und
β
j
−
β
i
=
q
t
n
+
t
.
. Wegen
a
n
g
n
∈{
−
}
=
=
Für die so erhaltenen Zahlen
s
,
t
gilt
s
,
t
0, . . . ,
n
1
1
(beachte den Satz 6.9 von Euler) gilt weiter:
a
α
i
−
α
j
g
β
j
−
β
i
a
s
a
q
s
n
+
s
g
q
t
n
+
t
g
t
.
=
=
=
=
=
Auf diese Weise erhält man die kleinsten positiven Zahlen
s
und
t
mit
a
s
g
t
.
=
Bei dieser Form des Algorithmus sind die Größen
x
0
,
x
1
,...,
x
i
,...,
x
j
zu spei-
chern. Nach dem Geburtstagsparad
oxo
n (siehe Aufgabe 2.2) erhält man die Zah-
len
i
x
j
etwa nach
<
j
mit
x
i
=
|
G
|
Schritten. Das Geburtstagsparadoxon ist
hier anwendbar, weil die Folge
wegen der Wahl der Rekursion eine
r Z
ufalls-
folge sehr ähnlich ist. Zeit- und Speicherkomplexität sind damit
O
(
x
i
)
(
|
|
)
.Wir
werden durch eine Modifikation des zweiten Schrittes im Abschnitt 10.3.2 die
Speicherkomplexität auf
O
G
(
)
1
bringen.
