Dialog Faktorisieren einer Zahl

Diesen Dialog erhält man über den Menüeintrag Einzelverfahren \ RSA-Kryptosystem \ Faktorisieren einer Zahl.

Den Vorgang des Aufspaltens natürlicher Zahlen in ihre Primfaktoren (Primfaktorzerlegung) bezeichnet man als Faktorisierung. Jede natürliche Zahl (die größer als 1 ist) lässt sich (bis auf die Reihenfolge der Primzahlfaktoren) eindeutig in ihre Primfaktoren zerlegen.

Das Faktorisierungsproblem stellt eine wichtige Schnittstelle zwischen Mathematik, Informatik und Technik dar, weil diese theoretische Fragestellung auch in der Kryptographie, wie beim RSA-Verfahren oder Rabin-Williams Verfahren, Anwendung findet.

Dieses Tutorial soll Ihnen einen Eindruck vermitteln, wie Faktorisierungsaufgaben in der Praxis angegangen werden.

faktorisierungsalgorithmen.gif

Sie haben verschiedene Faktorisierungsalgorithmen zur Zerlegung Ihrer Eingabe zur Auswahl.

Wenn Sie den Button Weiter drücken, wird mit den gewählten Algorithmen versucht, die Eingabe in zwei Faktoren aufzuspalten. Bei den ausgegebenen Faktorisierungsergebnissen werden die zusammengesetzten Faktoren rot markiert.

In diesem Dialog sind effiziente Verfahren zur Faktorisierung implementiert.

Es wird empfohlen, Brute-Force und Brent als "Vorstufe" zu verwenden, da diese Verfahren sehr schnell kleinere Faktoren finden. Will man die Zahl 10^40-1 faktorisieren, so reicht es, die Verfahren Brute-Force und Brent zu verwenden, da diese Eingabe nur "kleine" Primfaktoren besitzt,

Beispiel: 10^40-1

Mit Brute-Force,

bruteforce.gif

und dann mit Brent

brent.gif

Die Algorithmen Pollard‚s (p-1) bzw. Williams (p+1) führen mit großer Wahrscheinlichkeit

zum Erfolg, wenn die zu faktorisierende Zahl N einen Primfaktor p hat, so dass (p-1) bzw. (p+1) nur aus kleinen Primfaktoren besteht. Sie werden zur Abspaltung von Faktoren kleinerer Größe benutzt und daher stärkeren Verfahren zur Faktorisierung vorgeschaltet.

Beispiel: 233333330996666690033333333

pollard.gif

Der Algorithmus von Lenstra basiert auf einer Verallgemeinerung der Pollard‚s (p-1)-Methode auf elliptischen Kurven. Dieses Verfahren wird auch als ECM (Elliptic Curve Method) bezeichnet. Mit ECM kann man weitaus größere Faktoren abspalten. Trotzdem ist auch ECM nur für die Abspaltung von Faktoren mit bestimmten Eigenschaften geeignet. Diese Einschränkung führt dazu, dass "kleinere" Faktoren mit größerer Wahrscheinlichkeit gefunden werden als "große" Faktoren. Jedoch ist es wesentlich lohnenswerter, ECM statt der (p-1)-Methode einzusetzen.

Beispiel: 3035124991756191792335802070931

lenstraecm.gif

Sehr kleine Primteiler p einer Zahl n werden durch Probieren schneller aufgedeckt als mit ECM. Die Rechenzeit von ECM hängt hauptsächlich von der Größe des gesuchten Primteilers und kaum von der zu faktorisierenden Zahl ab. Wenn eine Zahl mit 1000 Dezimalstellen einen 20-stelligen Teiler hat, kann man ihn mit ECM finden. Andererseits wächst die Rechenzeit beträchtlich mit der Größe des kleinsten Faktors. ECM ist für Faktoren mit bis zu 30 Dezimalstellen geeignet. Der größte bisher mit diesem Verfahren gefundene Primfaktor hat 47 Dezimalstellen und wurde von Peter Montgomery am Zentrum für Mathematik und Informatik (CWI) in Amsterdam entdeckt.

Das quadratische Sieb ist geeignet zur Faktorisierung von Zahlen, die aus mehr als einem großen Faktor (mehr als 30 Stellen) zusammengesetzt sind.

Beispiel: 1999999999999999999077757777777777777777787

qsieb.gif

Die Rechenzeit ist dabei nicht abhängig vom kleinsten Faktor sondern von der zu faktorisierenden Zahl selbst. Das quadratische Sieb gehört – allerdings mit leichten Abwandlungen – zum schnellsten, was die Mathematiker an Faktorisierungsmethoden bisher "ausknobeln" konnten.

Obwohl sich damit derzeit Zahlen bis um 139 Dezimalstellen faktorisieren lassen, enthält auch dieses Verfahren noch zu viele Stellen, an denen man raten und suchen muss. Und dieses Raten und Suchen (bzw. der Verzicht auf das Raten zu Lasten des Suchens) dauern einfach zu lange, um ein wirklich effizientes Faktorisierungsverfahren zu ergeben.

Das quadratische Sieb wurde über viele Jahre als schnellstes Faktorisierungsverfahren betrachtet, bis vor wenigen Jahren NFS (Number Field Sieve) entdeckt wurde. NFS ist wie das quadratische Sieb ein Verfahren zur Faktorisierung großer Zahlen. NFS ist potenziell bis zu zehn mal schneller als das Quadratische Sieb. Allerdings können die bisher implementierten Algorithmen diesen potenziellen Geschwindigkeitsvorteil noch nicht voll nutzen. In den nächsten Jahren ist mit weiteren Optimierungen zu rechnen.

Die Faktorisierung vom RSA-155

Am 22. August 1999 veröffentlichte eine Forschergruppe, koordiniert von Herman te Riele vom CWI Amsterdam, die Faktorisierung der 512 Bit Zahl RSA-155 mit dem NFS-Algorithmus. RSA-155 stammt aus der "RSA-Challenge List" der Firma RSA Inc.

RSA-155 =10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897

= 102639592829741105772054196573991675900716567808038066803341933521790711307779 * 106603488380168454820927220360012878679207958575989291522270608237193062808643

Die Gesamtdauer zur Durchführung sämtlicher Schritte betrug 7,4 Monate (9 Wochen Vorberechnung und 5,2 Monate für die eigentliche Faktorisierung).

  1. Für den Siebungs-Schritt wurden 35.7 CPU-Jahre verwendet. Hierfür wurden folgende Rechner verwendet:

    160 * 175-400 MHz SGI und Sun workstations

    8 * 250 MHz SGI Origin 2000 processors

    120 * 300-450 MHz Pentium II PCs

    4 * 500 MHz Digital/Compaq boxes

    Dieser Aufwand war ungefähr äquivalent zu 8000 MIPS Jahren. 124.722.179 Relationen wurden gesammelt.

  2. Die resultierende Matrix hatte 6.699.191 Zeilen und 6.711.336 Spalten. Abgearbeitet wurde die Matrix in etwa 224 CPU Stunden mit einem Hauptspeicherbedarf von 2 Gbyte auf einer Cray C916 des SARA Amsterdam Academic Computer Center. Die Faktorisierung dauerte vom 17. März bis zum 22. August.

Den Siebungsschritt kann man praktisch beliebig parallelisieren. Insbesondere Organisationen mit unbeschränktem Hardwareetat können mit Spezialhardware (vgl. das optoelektronische TWINKLE-Device) die Faktorisierungsaufgabe stark beschleunigen.

Vgl. http://web.hamline.edu/~wnk/rsa/rsa.html (Factorization of a 512-bits RSA key using the Number Field Sieve)

Weitere Details siehe Skript, Kapitel 4.11.4.