Faktorisierungsverfahren

In der Zahlentheorie, einem Teilgebiet der Mathematik, versteht man unter einem Faktorisierungsverfahren, einen Algorithmus, der die Primfaktorzerlegung einer natürlichen Zahl berechnet. Bis zur Erfindung von Computern wurden Faktorisierungsverfahren nicht besonders intensiv untersucht, da es kaum praktische Anwendungen gab; man begnügte sich mit der Erkenntnis, dass zu jeder natürlichen Zahl eine eindeutige Primfaktorzerlegung existiert.

Heutzutage spielen Faktorisierungsverfahren eine wichtige Rolle in der Kryptologie und damit auch bei der Sicherheit im Internet. Dies liegt daran, dass es schnelle Primzahltests gibt, die entscheiden können, ob eine Zahl prim oder zusammengesetzt ist, jedoch kein annähernd so schnelles Faktorisierungsverfahren bekannt ist.

Die besten bekannten Algorithmen sind das 1981 von Carl Pomerance erfundene quadratische Sieb, das um 1990 von mehreren Leuten (u.a. Pollard, A. Lenstra, H.W. Lenstra Jr., Manasse, Pomerance) gemeinsam entwickelte Zahlkörpersieb und die Methode der Elliptischen Kurven, die 1987 von Hendrik W. Lenstra, Jr. vorgestellt wurde.

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.

Table of contents

1 Faktorisierungsverfahren mit exponentiellem Aufwand 2 Faktorisierungsverfahren mit subexponentiellem Aufwand 3 Sonstige Verfahren

Faktorisierungsverfahren mit exponentiellem Aufwand

• Probedivision.
• Faktorisieren mit Hilfe des Euklischen Algorithmus.
• Die Faktorisierungsmethode von Fermat.
• Die Faktorisierungsmethode von Lehman.
• Die Pollard Rho Methode.
• Die Pollard p-1 Methode.
• Die Pollard p+1 Methode.

Faktorisierungsverfahren mit subexponentiellem Aufwand

• Die Methode der Elliptischen Kurven.
• Die Kettenbruchmethode.
• Die Methode der Klassengruppen.
• Das Quadratische Sieb.
• Das Zahlkörpersieb.

Sonstige Verfahren

• Shors Algorithmus für Quantencomputer

---

Siehe auch: Geschichte der Faktorisierungsverfahren

---

Es fehlt noch: Faktorisiungsverfahren für andere Ringe, z.B. Polynomringe und Matrizenringe