Geschichte der Faktorisierungsverfahren
Dieser Artikel beschreibt die Geschichte der Faktorisierungsverfahren.
Table of contents |
2 17. bis 19. Jahrhundert 3 20. Jahrhundert, vor der Einführung von Computern 4 20. Jahrhundert, nach Einführung von Computern |
Seit Euklid von Alexandria ca. 300 Jahre vor Christus in seinem Hauptwerk, den Elementen, den Fundamentalsatz der Arithmetik formuliert und bewiesen hatte war bekannt, dass jede natürliche Zahl eine eindeutige Primfaktorzerlegung besitzt. Mit der Methode der Probedivision, die im wesentlichen ebenfalls schon Euklid bekannt war, hatte man schon sehr früh ein Verfahren gefunden, diese zu bestimmen, wenngleich es für größere Zahlen ungeeignet ist, da dann zu viel Zeit benötigt wird.
Im Jahre 1643 beschrieb Pierre de Fermat in einem Brief (der Adressat ist nicht bekannt, vermutlich Mersenne oder Frenicle) die heutzutage nach ihm benannte Methode von Fermat, die darauf basiert, dass man die zu faktorisierende Zahl als Differenz zweier Quadrate darstellt. Diese Methode, die vom Zeitaufwand eher schlechter als die Probedivision ist, bildet die Grundlage für nahezu alle modernen Faktorisierungsverfahren.
1926 veröffentlichte Maurice Kraitchik eine Arbeit, in der er einige Verbesserungen der Methode von Fermat vorschlägt. Insbesondere betrachtet er neben der zu faktorisierenden Zahl n auch deren Vielfache, anderst ausgedrückt, er sucht eine Kongruenz der Form x2 ≡ y2 (mod n). Um diese zu finden multipliziert er geeignete Kongruenzen der Form x2 ≡ y (mod n), die sich leicht und effektiv finden lassen (beschrieben im Artikel Quadratisches Sieb).
Derrick Lehmer und R. E. Powers schlugen 1931 eine andere Methode vor, um Kongruenzen der Form x2 ≡ y (mod n) zu finden. Diese bedient sich der Näherungsbrüche der Kettenbruchentwicklung von n.
Aufbauend auf der Idee von Lehmer und Powers entwickelte John Brillhart in den Sechzigern ein auf linearer Algebra über dem endlichen Körper F2 basierendes Verfahren um aus einer Liste von Kongruenzen der Form x2 ≡ y (mod n) geeignete auswählen zu können. Zusammen mit Michael Morrison galang ihm damit im Jahre 1975 die Faktorisierung der für damalige Zeit extrem großen 39-stelligen Fermat-Zahl F7. Insbesondere war es damit zum ersten mal gelungen, ein Faktorisierungsverfahren mit subexponentieller Laufzeit zu finden.
Inspiriert durch das lineare Sieb von Richard Schroeppel konnte Carl Pomerance 1981 eine Beschleunigung des Verfahrens erreichen, indem er ein Siebverfahren an Stelle der bis dato benutzten Probedivision einführte. Da das Siebverfahren sich nicht für die Kettenbruchmethode eignete ging Pomerance wieder zu dem ursprünglich von Kraitchik vorgeschlagenen Verfahren über. Hierdurch war es möglich geworden Zahlen mit bis zu 100 Stellen zu faktorisieren, insbesondere gelang es damit 1994 die 129stellige Zahl RSA-129 zu zerlegen. Dieses als quadratisches Sieb bezeichnete Verfahren ist heute noch das schnellste bekannte Verfahren zur Faktorisierung von Zahlen mit weniger als 100 Stellen.
In den Achzigerjahren vermutete man, dass Methoden, die auf der Idee von Kraitchik bassieren, nicht substantiell schneller als das quadratische Sieb sein können. Diese Vermutung wurde dadurch gestützt, dass es mittlerweile etliche Verfahren mit ähnlichen Laufzeiten gab und einem Ergebnis aus der analytischen Zahlentheorie über glatte Zahlen.
Anfang der Neunzigerjahre wurde diese Vermutung eindrucksvoll durch das Zahlkörpersieb widerlegt. Das Zahlkörpersieb wurde 1988 von John Pollard für spezielle Zahlen vorgeschlagen und danach von einer ganzen Reihe von Leuten (u.A. John Pollard, Arjen Lenstra, Hendrik Lenstra, Jr., Mark Manasse, Carl Pomerance, Joe Buhler, Len Adlemann) so verändert, dass es für beliebige Zahlen anwendbar wurde. Durch den Übergang zu algebraischen Zahlkörpern war es möglich geworden, die während der Rechnung benutzten Zahlen deutlich kleiner zu halten, und damit die erwähnte Beschleunigung zu erreichen. Insbesondere gelang damit 1990 die vollständige Faktorisierung der 155stelligen Fermat-Zahl F9.
Mit dem Gittersieb (einer von Pollard vorgeschlagenen Variante des Zahlkörpersiebs) gelang am 3. Dezember 2003 die Faktorisierung der bisher größten "schwer faktorisierbaren" Zahl RSA-576, die 174 Dezimalstellen besitzt.Faktorisierungsverfahren der Antike
17. bis 19. Jahrhundert
20. Jahrhundert, vor der Einführung von Computern
20. Jahrhundert, nach Einführung von Computern