Faktorisierungsverfahren

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

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

In der Praxis wird man um Zahl zu Faktorisieren wie folgt vorgehen:

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

Die ersten beiden Schritte werden dabei vertauscht.

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 Polynomringe und Matrizenringe

Bücher zum Thema Faktorisierungsverfahren

Dieser Artikel von Wikipedia unterliegt der GNU FDL.