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.

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.

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

• Shors Algorithmus für Quantencomputer

Siehe auch: Geschichte der Faktorisierungsverfahren

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