Faktorisierungsverfahren

Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie. Dabei soll zu einer zusammengesetzten Zahl ein nichttrivialer Teiler ermittelt werden. Ist beispielsweise die Zahl 91 gegeben, so sucht man eine Zahl wie 7, die 91 teilt. Entsprechende Algorithmen, die dies bewerkstelligen, bezeichnet man als Faktorisierungsverfahren. Durch rekursive Anwendung von Faktorisierungsverfahren in Kombination mit Primzahltests kann die Primfaktorzerlegung einer ganzen Zahl berechnet werden.

Bis heute ist kein Faktorisierungsverfahren bekannt, das nichttriviale Teiler und damit die Primfaktorzerlegung einer Zahl effizient berechnet. Das bedeutet, dass ein enormer Rechenaufwand notwendig ist, um eine Zahl mit mehreren hundert Stellen zu faktorisieren. Diese Schwierigkeit wird in der Kryptografie ausgenutzt. Die Sicherheit von Verschlüsselungsverfahren wie dem RSA-Kryptosystem beruht darauf, dass die Faktorisierung des RSA-Moduls zum Entschlüsseln der Nachrichten schwierig ist; somit würde ein effizientes Faktorisierungsverfahren zum Brechen des RSA-Verfahrens führen. Es ist jedoch denkbar, dass man das RSA-Problem effizienter als das Faktorisierungsproblem lösen kann. Jedoch ist bisher kein solches Verfahren bekannt.

In der theoretischen Informatik werden Probleme in Komplexitätsklassen eingeteilt, die darüber Aufschluss geben, welchen Aufwand die Lösung eines Problems erfordert. Beim Faktorisierungsproblem für ganze Zahlen ist nicht bekannt, welcher Komplexitätsklasse es angehört: Zwar ist bekannt, dass das Problem (in seiner Entscheidungsvariante) in der Klasse NP liegt, aber unbekannt, ob es bereits in polynomieller Zeit lösbar ist. Das heißt, es ist nach aktuellem Wissensstand nicht auszuschließen, dass irgendwann ein Algorithmus entdeckt wird, der ganze Zahlen mit überschaubarem Aufwand faktorisieren kann.

Die besten bekannten Algorithmen sind das 1981 von Carl Pomerance erfundene Quadratische Sieb, das um 1990 von mehreren Mathematikern gemeinsam entwickelte Zahlkörpersieb und die Methode der Elliptischen Kurven, die 1987 von Hendrik W. Lenstra, Jr. vorgestellt wurde.

Die RSA Factoring Challenge verfolgte bis zu ihrer Aussetzung im Jahre 2007 den aktuellen Forschungsstand auf dem Gebiet der Faktorisierungsverfahren. Daraus ergaben sich Anhaltspunkte für die notwendige Größe der im RSA-Kryptosystem verwandten Semiprimzahlen.

In der Praxis wird man, um eine Zahl zu faktorisieren, wie folgt vorgehen:

Durch Probedivision kleine Faktoren finden/entfernen.
Mit Hilfe eines Primzahltests herausfinden, ob die Zahl eine Primzahl oder eine Primpotenz ist.
Mit der Methode der Elliptischen Kurven nach vergleichsweise kleinen Primfaktoren (< 10³⁰) suchen.
Mit dem Quadratischen Sieb (für Zahlen mit weniger als 120 Dezimalstellen) oder dem Zahlkörpersieb faktorisieren.

Die ersten beiden Schritte werden dabei gelegentlich vertauscht.

Überblick der Faktorisierungsverfahren

Im Folgenden bezeichnet immer eine zusammengesetzte Zahl, für die ein Teiler ermittelt werden soll.

Probedivision

Das einfachste Verfahren zur Ermittlung eines Teilers von ist die Probedivision. Dabei wird durch alle Primzahlen beginnend mit der Zwei dividiert, bis sich eine Primzahl als deren Teiler erweist oder bis der Probedivisor größer als ${\sqrt n}$ ist. Das Verfahren ist zwar sehr aufwändig, eignet sich allerdings sehr gut zur Bestimmung kleiner Primfaktoren.

Berechnung des größten gemeinsamen Teilers

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 aus einem bestimmten Intervall findet. Dazu verwendet man das Produkt aller Primzahlen des Intervalls und berechnet den größten gemeinsamen Teiler der beiden Zahlen und . 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 $n/\operatorname {ggT}(n,m)$ anwenden muss, der viel kleiner als ist.

Faktorisierungsmethode von Fermat

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

Weitere Verfahren

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
Quadratisches Sieb
Zahlkörpersieb
Methode der elliptischen Kurven
Schnorrs Gitter-basiertes Faktorisierungsverfahren

Shor-Algorithmus

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 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 $({\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.

Geschichte

20. Jahrhundert, nach Einführung von Computern

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 Sechzigern 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 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 Achtzigerjahren 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 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 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₉.

Basierend auf einem Artikel in:

Wikipedia.de