Faktorisierungsverfahren

Das einfachste Verfahren zur Ermittlung eines Teilers von ${\displaystyle n}$ ist die Probedivision. Dabei wird ${\displaystyle n}$ durch alle Primzahlen beginnend mit der Zwei dividiert, bis sich eine Primzahl als deren Teiler erweist oder bis der Probedivisor größer als ${\displaystyle {\sqrt {n}}}$ geworden ist. Das Verfahren eignet sich sehr gut zur Bestimmung kleiner Primfaktoren, aber es ist sehr aufwändig, damit eine Zahl mit zwei oder mehr großen Primfaktoren vollständig zu zerlegen.

Die Probedivision kann durch den Euklidischen Algorithmus oder andere Verfahren zur Bestimmung des größten gemeinsamen Teilers so erweitert werden, dass man alle Primfaktoren von ${\displaystyle n}$ aus einem bestimmten Intervall findet. Dazu verwendet man das Produkt ${\displaystyle m}$ aller Primzahlen des Intervalls und berechnet den größten gemeinsamen Teiler der beiden Zahlen ${\displaystyle m}$ und ${\displaystyle n}$. Dieser ist das Produkt von Primfaktoren, die aus dem gewählten Intervall stammen, und man kann aus ihm die einzelnen Primfaktoren zurückgewinnen. Der Vorteil dieses Verfahrens liegt darin, dass man die Probedivision dann nur noch auf den Quotienten ${\displaystyle n/\operatorname {ggT} (n,m)}$ anwenden muss, der viel kleiner als ${\displaystyle n}$ ist.[1]

Ein Verfahren, das sich besonders gut eignet, um Teiler in der Nähe von ${\displaystyle {\sqrt {n}}}$ zu finden, ist die Faktorisierungsmethode von Fermat. Dieser Algorithmus funktioniert nur für ungerade ${\displaystyle n}$ und nutzt aus, dass sich diese als Differenzen zweier Quadratzahlen darstellen lassen. Er berechnet zuerst die kleinste ganze Zahl ${\displaystyle x}$, die größer oder gleich ${\displaystyle {\sqrt {n}}}$ ist. Anschließend berechnet der Algorithmus die Differenzen ${\displaystyle x^{2}-n}$, ${\displaystyle (x+1)^{2}-n}$, ${\displaystyle (x+2)^{2}-n}$ …, bis eine dieser Differenzen eine Quadratzahl ist. Aus dieser werden Teiler von ${\displaystyle n}$ berechnet.

• Faktorisierungsmethode von Lehman
• Kettenbruchmethode
• Pollard-p−1-Methode
• Pollard-p+1-Methode
• Pollard-Rho-Methode
• Dixons Faktorisierungsmethode (random squares method)
• Methode der Klassengruppen von Daniel Shanks, mit Varianten von Martin Seysen (class group relations method) und Lenstra/Schnorr (random class groups method)
• SQUFOF, square form factorization von Shanks[2]
• Quadratisches Sieb
• Zahlkörpersieb
• Methode der elliptischen Kurven
• Schnorrs Gitter-basiertes Faktorisierungsverfahren[3]

Eine besondere Stellung unter den Faktorisierungsverfahren nimmt der Shor-Algorithmus ein. Er kann nicht auf klassischen Rechnern ausgeführt werden, sondern benötigt einen Quantencomputer. Auf diesem kann er jedoch in Polynomialzeit einen Faktor von ${\displaystyle n}$ berechnen. Allerdings können noch keine Quantencomputer gebaut werden, die über eine für die Faktorisierung großer Zahlen ausreichende Registergröße verfügen. Die Funktion des Shor-Algorithmus beruht darauf, die Ordnung eines Elements der primen Restklassengruppe ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ mit Hilfe der Quanten-Fouriertransformation zu bestimmen.

Nach Bekanntwerden des Shor-Algorithmus entwickelten Physiker technische Systeme und Versuchsanordnungen, die auf klassischem Weg, ohne Überlagerung von Quantenzuständen, die Faktorisierung natürlicher Zahlen ermöglichen. Dazu gehören z. B. Kernspinresonanz[4], kalte Atome[5], ultrakurze Lichtpulse[6] und Mehrweg-Interferometrie[7][8].

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 Marin Mersenne oder Bernard Frénicle de Bessy) die heutzutage nach ihm benannte Faktorisierungsmethode 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 Faktorisierungsmethode von Fermat vorschlägt. Insbesondere betrachtet er neben der zu faktorisierenden Zahl n auch deren Vielfache, anders ausgedrückt, er sucht eine Kongruenz der Form x² ≡ y² (mod n). Um diese zu finden, multipliziert er geeignete Kongruenzen der Form x² ≡ y (mod n), die sich leicht und effektiv finden lassen (beschrieben im Artikel Quadratisches Sieb).

Derrick Henry Lehmer und Ralph Ernest Powers schlugen 1931 die sogenannte Kettenbruchmethode vor, um Kongruenzen der Form x² ≡ y (mod n) zu finden.

Mit der Einführung von Computern begann die intensive Erforschung von Faktorisierungsverfahren. Aufbauend auf der Idee von Lehmer und Powers entwickelte John Brillhart in den 1960er Jahren ein auf linearer Algebra über dem endlichen Körper F₂ basierendes Verfahren, um aus einer Liste von Kongruenzen der Form x² ≡ y (mod n) geeignete auswählen zu können. Zusammen mit Michael Morrison gelang ihm damit im Jahre 1975 die Faktorisierung der für damalige Zeit extrem großen 39-stelligen Fermat-Zahl F₇. Insbesondere war es damit zum ersten Mal gelungen, ein Faktorisierungsverfahren mit subexponentieller Laufzeit (der Stellenanzahl) 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 129-stellige 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 1980er Jahren vermutete man, dass Methoden, die auf der Idee von Kraitchik basieren, nicht substanziell schneller als das quadratische Sieb sein können. Diese Vermutung wurde dadurch gestützt, dass es mittlerweile etliche Verfahren mit ähnlichen Laufzeiten gab, und durch ein Ergebnis aus der analytischen Zahlentheorie über glatte Zahlen.

Anfang der 1990er Jahre wurde diese Vermutung durch das Zahlkörpersieb eindrucksvoll widerlegt. Das Zahlkörpersieb wurde 1988 von John Pollard für spezielle Zahlen vorgeschlagen und danach von einer ganzen Reihe von Mathematikern (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 155-stelligen Fermat-Zahl F₉.

Mit dem Gittersieb (einer von Pollard vorgeschlagenen Variante des Zahlkörpersiebs) und anderen Methoden wurde 2005 die Faktorisierung der bislang größten aus zwei großen Primfaktoren zusammengesetzten Zahl (einer sogenannten Fastprimzahl) ohne spezielle Struktur nach zweijähriger Arbeit auf einem Rechnerpool fertiggestellt. Dabei handelt es sich um die Zahl RSA-200, eine 200-stellige Dezimalzahl, die gemeinsam mit vielen anderen Semiprimzahlen im Rahmen der RSA Factoring Challenge generiert wurde.

Im Jahr 2012 faktorisierte eine Gruppe von 500 Teilnehmern am BOINC-Projekt NFS@Home eine Zahl mit 211 Dezimalziffern und entschlüsselte damit eine Geheimbotschaft, die im Jahr 1997 von Donald Knuth in dem Buch The Art of Computer Programming als seinerzeit unlösbare Aufgabe gestellt wurde. Knuth ersetzte daraufhin das Problem unter Verwendung einer Semiprimzahl mit 318 Dezimalziffern.[9]

Die Liste von Champions im nach Allan Joseph Champneys Cunningham benannten Cunningham-Projekt listet aktuelle Faktorisierungsrekorde für verschiedene Zerlegungsverfahren auf.[10]