Cryptography Reference
In-Depth Information
x
2
Wir definieren die Zahlenfolge
(
x
i
)
rekursiv mit einer Abbildung
f
(
x
)=
+
c
,
∈
Z
\{
−
}
wobei
c
0,
2
(siehe Aufgabe 11.1), und einem Startwert
x
0
:
x
i
+
1
=
f
(
x
i
)
.
=
Diese spezielle Wahl von
f
hat sich in der Praxis bewährt, häufig wird
c
1
gewählt. Im folgenden Algorithmus benutzen wir Lemma 10.2, um einen nicht-
trivialen Teiler
d
von
N
zu bestimmen.
∈{
−
}
∈
Z
\{
−
}
Wähle ein
x
0
0, . . . ,
N
1
und ein
c
0,
2
.
=
(
)
=
(
(
))
Berechne
x
1
f
x
0
und
x
2
f
f
x
0
modulo
N
.
Falls 1
<
d
=
ggT
(
x
2
−
x
1
,
N
)
, Stop!, sonst:
Berechne
x
2
=
f
(
x
1
)
und
x
4
=
f
(
f
(
x
2
))
modulo
N
.
Falls 1
<
d
=
ggT
(
x
4
−
x
2
,
N
)
, Stop!, sonst:
=
(
)
=
(
(
))
Berechne
x
3
f
x
2
und
x
6
f
f
x
4
modulo
N
.
<
=
(
−
)
Falls 1
d
ggT
x
6
x
3
,
N
, Stop!, usw.
Der Algorithmus terminiert nach Lemma 10.2. In dem seltenen Fall
d
N
,in
dem nichts gewonnen ist, wähle man ein neues
c
und starte erneut. Die Wahl
eines neuen Starwertes
x
0
empfielt sich nicht. Der Fall
d
=
=
N
tritt ein, wenn für
alle Primteiler von
N
gleichzeitig Treffer auftreten.
Beispiel
Wir suchen einen nichttrivialen Teiler der (zusammengesetzten) Zahl
N
=
1 517.
x
2
Für
c
wählen wir 1, d. h.
f
(
x
)=
+
1, und als Startwert wählen wir
x
0
=
70.
x
1
=
350
x
2
=
1141
ggT
(
1141
−
350, 1517
)=
1
x
2
=
1141
x
4
=
1148
ggT
(
1148
−
1141, 1517
)=
1
x
3
=
296
x
6
=
412
ggT
(
412
−
296, 1517
)=
1
x
4
=
1148
x
8
=
1010
ggT
(
1010
−
1148, 1517
)=
1
x
5
=
1149
x
10
=
196
ggT
(
196
−
1149, 1517
)=
1
x
6
=
412
x
12
=
862
ggT
(
862
−
412, 1517
)=
1
x
7
=
1358
x
14
=
825
ggT
(
825
−
1358, 1517
)=
41
=
·
Damit ist 1 517
37
41 zerlegt.
11.3 Pollards
p
−
1
-Methode
Mit der
p
1 Produkt von
kleinen Primzahlen ist. Dabei spielt die Größe von
p
kaum eine Rolle.
−
1-Methode findet man Primteiler
p
von
N
, für die
p
−
