Faktorisierungsverfahren – einfach erklärt

Grundidee, Bedeutung und Schwierigkeit

Das Faktorisierungsproblem ist eine Aufgabe der Zahlentheorie: Zu einer zusammengesetzten ganzen Zahl soll ein nichttrivialer Teiler gefunden werden, also ein Teiler außer 1 und der Zahl selbst. Bei 91 ist beispielsweise 7 ein solcher Teiler. Algorithmen dafür heißen Faktorisierungsverfahren. Wendet man sie wiederholt an und verbindet sie mit Primzahltests, erhält man die vollständige Primfaktorzerlegung.

Für große Zahlen ist die Faktorisierung sehr rechenaufwendig. Bis heute ist kein Verfahren bekannt, das nichttriviale Teiler einer beliebigen Zahl mit mehreren hundert Stellen effizient auf einem klassischen Computer bestimmt. Diese Schwierigkeit ist für die Kryptografie wichtig: Die Sicherheit des RSA-Kryptosystems beruht darauf, dass sich der verwendete RSA-Modul nur schwer faktorisieren lässt. Ein effizientes allgemeines Faktorisierungsverfahren könnte RSA brechen. Denkbar ist zwar, dass sich das eigentliche RSA-Problem leichter lösen lässt als das Faktorisierungsproblem; ein solches Verfahren ist aber nicht bekannt.

Auch die theoretische Einordnung ist offen. Die Entscheidungsvariante des Faktorisierungsproblems liegt in der Komplexitätsklasse NP. Unbekannt ist jedoch, ob sie in polynomieller Zeit lösbar ist, also mit einem Aufwand, der nur polynomial mit der Eingabegröße wächst. Daher kann nicht ausgeschlossen werden, dass künftig ein wesentlich effizienterer Algorithmus entdeckt wird.

Zu den wichtigsten bekannten klassischen Verfahren gehören das 1981 von Carl Pomerance erfundene Quadratische Sieb, das um 1990 von mehreren Mathematikern entwickelte Zahlkörpersieb und die 1987 von Hendrik W. Lenstra, Jr. vorgestellte Methode der elliptischen Kurven. Die bis 2007 durchgeführte RSA Factoring Challenge dokumentierte den Forschungsstand und lieferte Anhaltspunkte dafür, wie groß die in RSA verwendeten Semiprimzahlen sein müssen. Eine Semiprimzahl ist hier eine Zahl aus zwei Primfaktoren.

Praktisches Vorgehen und grundlegende Methoden

In der Praxis kombiniert man mehrere Verfahren:

• Zunächst werden durch Probedivision kleine Faktoren gesucht und entfernt. • Ein Primzahltest prüft, ob die verbleibende Zahl eine Primzahl oder eine Primpotenz ist. Eine Primpotenz hat die Form p^k mit einer Primzahl p. • Die Methode der elliptischen Kurven sucht nach vergleichsweise kleinen Primfaktoren unter 10^30. • Danach verwendet man für Zahlen mit weniger als 120 Dezimalstellen das Quadratische Sieb oder andernfalls das Zahlkörpersieb.

Die ersten beiden Schritte werden gelegentlich vertauscht.

Bei der Probedivision wird die zusammengesetzte Zahl n nacheinander durch alle Primzahlen ab 2 geteilt. Man beendet die Suche, sobald ein Teiler gefunden wurde oder der Probedivisor größer als √n ist. Das Verfahren eignet sich gut für kleine Primfaktoren, ist aber sehr aufwendig, wenn n aus zwei oder mehr großen Primfaktoren besteht.

Eine Erweiterung nutzt den größten gemeinsamen Teiler, kurz ggT. Man bildet das Produkt m aller Primzahlen aus einem gewählten Intervall und berechnet ggT(n,m), beispielsweise mit dem Euklidischen Algorithmus. Das Ergebnis ist das Produkt derjenigen Primfaktoren von n, die im Intervall liegen. Daraus lassen sich die einzelnen Primfaktoren zurückgewinnen. Anschließend muss die Probedivision nur noch auf den kleineren Quotienten n/ggT(n,m) angewendet werden.

Fermats Methode und weitere klassische Verfahren

Die Faktorisierungsmethode von Fermat eignet sich besonders für Faktoren in der Nähe von √n. Sie funktioniert nur für ungerade n und verwendet die Darstellung einer Zahl als Differenz zweier Quadrate. Zunächst bestimmt man die kleinste ganze Zahl x mit x ≥ √n. Danach untersucht man nacheinander x²−n, (x+1)²−n, (x+2)²−n und so weiter, bis eine dieser Differenzen eine Quadratzahl ist. Aus dieser Darstellung können Teiler von n berechnet werden.

Weitere Faktorisierungsverfahren sind die Faktorisierungsmethode von Lehman, die Kettenbruchmethode, die Pollard-p−1-, Pollard-p+1- und Pollard-Rho-Methode, Dixons Faktorisierungsmethode, die Methode der Klassengruppen von Daniel Shanks und ihre Varianten, SQUFOF, das Quadratische Sieb, das Zahlkörpersieb, die Methode der elliptischen Kurven sowie Schnorrs gitterbasiertes Faktorisierungsverfahren. Die Verfahren sind für unterschiedliche Zahlenstrukturen und Faktorgrößen geeignet; deshalb werden sie in der Praxis kombiniert.

Quantencomputer und Shor-Algorithmus

Der Shor-Algorithmus nimmt eine Sonderstellung ein. Er ist nicht für klassische Rechner bestimmt, sondern benötigt einen Quantencomputer. Darauf kann er einen Faktor von n in Polynomialzeit berechnen. Allerdings lassen sich bislang keine Quantencomputer mit einer Registergröße bauen, die zur Faktorisierung großer Zahlen ausreicht.

Das Verfahren bestimmt mithilfe der Quanten-Fouriertransformation die Ordnung eines Elements der primen Restklassengruppe (ℤ/nℤ)×. Die Ordnung ist die kleinste positive Anzahl von Multiplikationen, nach der eine Potenz des Elements wieder 1 ergibt. Aus dieser Information lässt sich ein Faktor von n gewinnen.

Nach der Veröffentlichung des Shor-Algorithmus wurden außerdem technische Systeme und Versuchsanordnungen entwickelt, die natürliche Zahlen auf klassischem Weg und ohne Überlagerung von Quantenzuständen faktorisieren. Genannt werden Kernspinresonanz, kalte Atome, ultrakurze Lichtpulse und Mehrweg-Interferometrie.

Historische Entwicklung bis zum Zahlkörpersieb

Euklid von Alexandria formulierte und bewies etwa 300 v. Chr. in den Elementen den Fundamentalsatz der Arithmetik: Jede natürliche Zahl besitzt eine eindeutige Primfaktorzerlegung. Auch die Probedivision war ihm im Wesentlichen bereits bekannt, ist für große Zahlen jedoch zu langsam.

1643 beschrieb Pierre de Fermat in einem Brief seine Methode, eine Zahl als Differenz zweier Quadrate darzustellen. Obwohl sie hinsichtlich des Zeitaufwands eher schlechter als die Probedivision ist, bildet ihre Grundidee die Basis nahezu aller modernen Faktorisierungsverfahren.

Maurice Kraitchik schlug 1926 Verbesserungen vor. Er betrachtete auch Vielfache von n und suchte Kongruenzen der Form x² ≡ y² (mod n). Eine Kongruenz bedeutet hier, dass beide Seiten bei Division durch n denselben Rest besitzen. Kraitchik erzeugte sie durch Multiplikation leicht auffindbarer Kongruenzen x² ≡ y (mod n). Derrick Henry Lehmer und Ralph Ernest Powers entwickelten 1931 dafür die Kettenbruchmethode.

Nach Einführung der Computer wurde die Forschung intensiviert. John Brillhart nutzte in den 1960er Jahren lineare Algebra über dem endlichen Körper F₂, um passende Kongruenzen auszuwählen. Gemeinsam mit Michael Morrison faktorisierte er 1975 die 39-stellige Fermat-Zahl F₇. Damit stand erstmals ein Faktorisierungsverfahren mit subexponentieller Laufzeit bezogen auf die Stellenzahl zur Verfügung.

Carl Pomerance ersetzte 1981 die zuvor verwendete Probedivision durch ein Siebverfahren und kehrte dabei zu Kraitchiks Ansatz zurück. Das daraus entstandene Quadratische Sieb ermöglichte Faktorisierungen von Zahlen mit bis zu 100 Stellen. 1994 wurde damit RSA-129 mit 129 Stellen zerlegt. Der Artikel bezeichnet das Quadratische Sieb als schnellstes bekanntes Verfahren für Zahlen mit weniger als 100 Stellen.

Die Annahme, Kraitchiks Grundidee könne nicht wesentlich verbessert werden, wurde Anfang der 1990er Jahre durch das Zahlkörpersieb widerlegt. John Pollard hatte es 1988 zunächst für spezielle Zahlen vorgeschlagen; anschließend wurde es für beliebige Zahlen erweitert. Durch algebraische Zahlkörper bleiben die während der Berechnung verwendeten Zahlen kleiner. 1990 gelang damit die vollständige Faktorisierung der 155-stelligen Fermat-Zahl F₉.

Rekorde und Implementierungen

Mit dem Gittersieb, einer von Pollard vorgeschlagenen Variante des Zahlkörpersiebs, und weiteren Methoden wurde 2005 nach zweijähriger Arbeit auf einem Rechnerpool RSA-200 faktorisiert. Die 200-stellige Dezimalzahl war damals die größte ohne spezielle Struktur faktorisierte Zahl, die aus zwei großen Primfaktoren bestand.

2012 zerlegte eine Gruppe von 500 Teilnehmenden des BOINC-Projekts NFS@Home eine Zahl mit 211 Dezimalziffern. Damit entschlüsselte sie eine Geheimbotschaft, die Donald Knuth 1997 in The Art of Computer Programming als damals unlösbare Aufgabe gestellt hatte. Knuth ersetzte sie anschließend durch eine Aufgabe mit einer Semiprimzahl aus 318 Dezimalziffern. Das Cunningham-Projekt führt aktuelle Rekorde verschiedener Faktorisierungsverfahren.

Als konkrete Implementierung enthält das Programm ARIBAS von Otto Forster mehrere der beschriebenen Verfahren, teils in seiner Laufzeitbibliothek und teils als Ergänzung zu Forsters Buch über Algorithmische Zahlentheorie.