Cryptography Reference
In-Depth Information
oder - etwas schlampig -
N
sei faktorisiert. Um eine Zerlegung von
N
zu bestim-
men, hat sich das folgende Vorgehen bewährt.
Prüfe, ob
N
durch eine Primzahl
p
kleiner einer festgelegten Schranke
B
teilbar
ist.
Dazu bestimmt man (oder hat schon gespeichert) eine Liste aller Primzahlen
≤
B
und berechnet sukzessive den Rest von
N
bei Division durch
p
. Ist er 0
wird
p
ausgegeben - Stop!
Will man nur wissen, ob solche Primteiler existieren, berechnet man
d
=
(
)
≤
ggT
B
ist. Diese Vorgehenswei-
se ist insbesondere dann vorteilhaft, wenn nicht damit gerechnet werden
muss, dass es solche Primzahlen gibt.
R
,
N
, wobei
R
Produkt aller Primzahlen
Falls keine solchen Primteiler gefunden werden:
Prüfe, ob
N
eine Primzahl ist (vgl. Kapitel 8 über Primzahltests). Falls ja -
Stop!; falls nein:
Prüfe, ob
N
Potenz einer natürlichen Zahl ist (vgl. Aufgabe 8.6). Falls ja - Stop!;
falls nein:
Erst jetzt bringt man die schweren Geschütze ins Spiel, die wir in den folgen-
den Abschnitten besprechen. Dabei empfiehlt sich im Allgemeinen die Rei-
henfolge (wobei nicht alle Verfahren angewendet werden müssen):
−
p
1 -Methode mit kleiner Schranke
B
,
Pollards
-Methode,
Kettenbruchmethode,
die elliptische Kurven Methode nach Lenstra (siehe Abschnitt 14.3),
quadratisches Sieb,
Zahlkörpersieb.
Bemerkung
Das
Zahlkörpersieb
werden wir in diesem Buch nicht behandeln, es sind hierzu
weit mehr Hilfsmittel aus der Algebra nötig als wir zur Verfügung haben.
Die Schranke
B
, bis zu der Probedivisionen durchgeführt werden, hängt sehr von
der Anwendung ab. MAPLE benutzt
B
=
=
100 000, Cohen [7] schlägt
B
500 000
vor und diskutiert größere Schranken.
Für den Rest dieses Kapitels setzen wir
N
als zusammengesetzte natürliche Zahl
voraus, d. h.
N
ist ungleich 1 und keine Primzahl. Unser Ziel ist es, einen nicht-
trivialen Teiler
d
von
N
zu finden.
