Cryptography Reference
In-Depth Information
11.3.3 Der Algorithmus
Im nachfolgenden Algorithmus wird es deutlich, wie man
a
λ
(
B
)
sukzessive aus-
rechnet. Die Eingabe ist die natürliche Zahl
N
, die es zu faktorisieren gilt. Die
Ausgabe ist ein echter Teiler von
N
oder
Pech gehabt
.
Wähle
B
und bestimme alle Primzahlen
p
1
,...,
p
n
kleiner gleich
B
,am
Besten beginnend mit
p
1
∈
N
=
2 der Größe nach geordnet.
maximal mit
p
ν
i
i
Wähle
ν
i
∈
N
≤
B
für alle
i
∈{
1, . . . ,
n
}
.
∈
N
>
1
mit ggT
(
)=
Wähle
a
0
a
0
,
N
1.
a
p
ν
i
≡
(
)
<
<
=
Berechne iterativ
a
i
i
mod
N
mit 0
a
i
N
für
i
1,...,
n
und
i
−
1
bestimme
d
:
=
ggT
(
a
i
−
1,
N
)
.
=
Falls
d
1 nächstes
i
.
>
Falls
d
1 nächster Schritt.
Falls
d
=
N
, gib
d
zurück, sonst
Pech gehabt
.
=
(
−
)=
Falls stets
d
1, d. h. ggT
a
n
1,
N
1, dann gibt es keinen
B
-glatten Prim-
teiler von
N
-
Pech gehabt
.
Im sehr seltenen Fall, dass
d
N
ist, lohnt es sich evtl. den Algorithmus mit
einem neuen Startwert
a
0
nochmals zu durchlaufen. Im übrigen bedeutet
d
=
=
N
,
−
dass es Primteiler
p
von
N
gibt, für die
p
1
B
-potenzglatt ist.
Bemerkung
In MAPLE wurde beispielsweise
B
2000 gewählt. Cohen [7] schlägt
B
zwischen
10
5
und 10
6
vor. Die Wahl von
B
beeinflusst stark die Laufzeit, aber auch die
Wahrscheinlichkeit, eine Zerlegung zu finden.
=
Die
p
−
1 -Methode von Pollard wird manchmal mit einer kleinen Schranke wie
=
2 000 angewendet, um
relativ kleine
Primteiler zu finden. Die Methode ist
aber auch von theoretischem Interesse, weil sie
B
•
die Idee liefert für Lenstras Elliptische Kurven Methode (siehe Kapitel 14).
•
einen Angriff auf das RSA-Verfahren darstellt. Wie schon in Abschnitt 7.4.1
erwähnt, sollte die Primzahlen
p
und
q
so gewählt werden, dass
p
−
1 und
q
−
1 jeweils einen
großen
Primteiler haben.
+
•
eine Verallgemeinerung besitzt zur sogenannten
p
1
-Methode
, die eben-
falls Auswirkungen auf die Wahl der Primzahlen bei RSA hat. Siehe auch
dazu Abschnitt 7.4.1.
