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 (u. a. John M. Pollard, Arjen Lenstra, Hendrik Lenstra Jr., Mark S. Manasse, Carl Pomerance) 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:

1. Durch Probedivision kleine Faktoren finden/entfernen.
2. Mit Hilfe eines Primzahltests herausfinden, ob die Zahl eine Primzahl oder eine Primpotenz ist.
3. Mit der Methode der elliptischen Kurven nach vergleichsweise kleinen Primfaktoren (<10³⁰) suchen.
4. 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.