Faktorisierung von Zahlen

„Dass die Aufgabe, die Primzahlen von den zusammengesetzten zu unterscheiden und letztere in ihre Primfaktoren zu zerlegen zu den wichtigsten und nützlichsten der gesamten Arithmetik gehört und die Bemühungen und den Scharfsinn sowohl der alten wie auch der neueren Geometer in Anspruch genommen hat, ist so bekannt, dass es überflüssig wäre, hierüber viele Worte zu verlieren.“
Gauß 1801 in „Disquisitiones Arithmeticae“

Faktorisierung von ZahlenEines der anspruchsvollsten mathematischen und rechentechnischen Probleme ist die Faktorisierung sehr großer Zahlen. Mehr als 150-stellige Zahlen sind heutzutage nur auf Supercomputern in vertretbarer Zeit faktorisierbar.
Dabei ist es nicht mehr möglich, die gegebene Zahl mittels Testdivisionen zu zerlegen. Für eine nur 18-stellige Zahl wären dies; ohne Berücksichtigung von besonderen Zahleigenschaften – etwa 500 Millionen Divisionen. Einen Ausweg aus dem Problem bieten zwei Verfahren.

Nach dem sogenannten „Kleinen Satz von Fermat“ lässt die Potenz ap-1 für jede natürliche Basis a < p bei Division mit p den Rest 1, wenn p eine Primzahl ist, d.h.

    \[ 2^{p-1}\mod p =1 \quad bzw. \quad 2^p\mod p = 2 \]

Liegt also eine natürliche Zahl n vor, für welche 2n mod n nicht den Rest 2 liefert, so ist n mit Sicherheit keine Primzahl. Leider kann aus dem Rest kein Schluss über einen Teiler gezogen werden. Leider gilt die Umkehrung nicht.

Dieses Teilprogramm faktorisiert eine bis zu 100-stellige Zahl n.
Für diese wird nach dem kleinen Satz von Fermat ein Primzahltest durchgeführt. Ergibt sich, dass die Zahl n wahrscheinlich eine Primzahl ist, wird ein weiterer, aufwendigerer Test gestartet, der BPSW-Test. Dieser wurde 1980 von Baillie, Wagstaff und Pomerance entwickelt.
Bis heute ist keine zusammengesetzte Zahl bekannt, bei der dieser Test versagt.
Sollte der Test keine Zerlegbarkeit nachweisen, wird die Faktorisierung abgebrochen.

Ist bekannt, dass eine Zahl n zerlegbar ist, kann nach Primteilern gesucht werden. Je nach Größe der Zahl existieren effiziente Möglichkeiten, die Faktoren zu finden. In diesem Teilprogramm werden vier Verfahren eingesetzt:

  • Probedivision mit allen Primzahlen bis 1 Million
  • Pollard-Rho-Verfahren
  • Faktorisierung mit elliptischen Kurven
  • Faktorisierung mit einem quadratischen Sieb

Pollard-Rho-Verfahren

Ein schnelles Verfahren ist eine Monte-Carlo-Methode, welche von Pollard entwickelt wurde.

Will man einen Primfaktor p der Zahl n gewinnen, so sucht man nach einem Paar a,b, sodass p | (a – b). Über den ggT von a – b und n lässt sich dann p ermitteln (p muss nicht notwendigerweise der kleinste Primteiler sein). Das Paar a,b wird nun mittels Zufallsgenerator bestimmt, bis a und b kongruent mod p sind. Nach der Theorie sind im Mittel \sqrt{\frac{\pi p}{2}} Paare zu testen. Passende Paare ergeben sich mittels Floyds Zyklenalgorithmus f(x) = x² + a, mit a <> 0 und a <> -2.

Das wirklich Verblüffende daran ist, dass dieses Verfahren nur sehr selten versagt. Während etwa 5 · 107 Testdivisionen für die z.B. 17-stellige Zahl 11111111111111111 notwendig sind, genügen im Mittel nach Pollard nur wenige.

Vorsicht ist aber dennoch geboten: Der Vorteil einer geringeren Anzahl von Tests wird durch den erhöhten Aufwand für kleine Zahlen bis etwa 8-9 Stellen wieder aufgehoben. Erst jenseits von 15 Ziffern kommt das Verfahren voll zur Wirkung, allerdings sind andere Verfahren ab 20 Stellen noch effektiver. In diesem Unterprogramm können Sie nach dem Fermat-Primzahltest Teiler der Zahl mittels Pollard-ρ-Verfahren und einem von Brent modifizierten Verfahren suchen lassen.

Methode mit elliptischen Kurven

Durch Lenstra wurde ein hoch interessantes Faktorisierungsverfahren entwickelt.
Um einen Primteiler p zu finden, betrachtet man Punkte (x, y) der Form

    \[ y^2=x^3+ax+b \]

wobei x, y aus dem Restklassenring modulo p und a, b ganze Zahlen sind. Man kann zeigen, dass diese elliptische Kurve eine abelsche Gruppe ist, d.h. es ist möglich, beliebige Punkte auf der Kurve zu addieren bzw. zu invertieren.

Um p zu finden, wird nun versucht, das neutrale Element Op durch Punktadditionen zu konstruieren. Ob das gelingt, hängt entscheidend von der Gruppenordnung ab. Sind alle ihre Primteiler kleiner als eine Schranke b, so hat man eine Chance. Über die Kurvenparameter kann auf die Ordnung Einfluss genommen werden, wobei der Effekt nicht vorhersagbar ist.
Die optimalen Werte für die genutzten Schranken hängen von der Größe des zu findenden Primteilers p ab, der allerdings nicht bekannt ist. Daher ist das Auffinden eines Primteilers nicht sicher.

Obwohl die Methode der elliptischen Kurven asymptotisch langsamer ist, als das Faktorisieren mit einem quadratischen Sieb, ist das Lenstra-Verfahren wesentlich effektiver als das Pollard-Faktorisierungsverfahren.

Ein quadratisches Sieb ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer natürlicher Zahlen. 1981 wurde diese Verfahren von Richard Schroeppel und Carl Pomerance entwickelt.

Das Besondere ist, dass die Laufzeit von der Größe der zu faktorisierenden Zahl abhängt und nicht von speziellen Eigenschaften der Zahl. Für Zahlen von 40 bis 100 Dezimalstellen ist es das schnellste allgemeine Faktorisierungsverfahren. Ist n die zu zerlegende Zahl, so ist die Laufzeit von der Ordnung e^{\sqrt{\ln{n}\ln{\ln{n}}}}.

Bei der von J.A.David und D.B.Holdridge gefundenen Weiterentwicklung, dem Multiple Polynomial Quadratic Sieve (MPQS), definiert man verschiedene Funktionen, die jeweils einen festen Faktor enthalten. Aus deren Eigenschaften gewinnt man spezielle Relationen, aus denen wiederum der gesuchte Faktor bestimmt wird. Die Beschreibung des Verfahrens ist sehr anspruchsvoll. Weitere Erklärungen sind in entsprechender Fachliteratur zu finden.

Nach dem Siebvorgang muss außerdem zeitaufwändig ein Gleichungssystem gelöst werden, dass bei 70stelligen und größeren Zahlen aus mehr als 10000 Variablen und 10000 Gleichungen besteht.

Beachten Sie bitte: Auch wenn MPQS zu den schnellsten Faktorisierungsverfahren gehört, ist die Zerlegung einer mehr als 80stelligen mit diesem Teilprogramm eine zeitaufwendige Herausforderung. Eine 90stellige Zahl benötigt zum Beispiel etwa zehnmal so viel Zeit, wie eine 80stellige. Für eine 100stellige erhöht sich der Aufwand sogar auf die 80fache Zeit.

Die Grenze dieses Teilprogramms liegt bei etwa 90stelligen Zahlen.
Für die Zerlegung der Zahl
25389739913858345524208216151645759882986445317021182277812631082013053557679073
mit 80 Stellen ergab sich auf einem Testrechner:
= 5784129575911828826747325399392132675137 (40) ·
· 4389552408990738265259608301074256807329 (40)
Zeit: 28min 16,2040s

Mit der Laufzeitabschätzung würde also für eine 100stellige Zahl in diesem Programm eine Berechnungszeit von etwa 60 Stunden auftreten.
Wenn man bedenkt, dass man 1977 für die Faktorisierung einer 100-stelligen Zahl 40 Billiarden Jahre schätzte und 1994 noch 8 Monaten auf 1600 Internet-Rechnern benötigt wurden, so ist die Entwicklung sehr beeindruckend.

Allerdings ist diese Faktorisierungsroutine dennoch 20mal langsamer als das schnellste gegenwärtig im Internet verfügbare Programm „yafu-x64“. „yafu“ benutzt ein selbstinitialisierendes quadratisches Sieb (SIQS) und ein Zahlkörpersieb (GNFS), die beide Weiterentwicklungen des MPQS-Verfahrens sind.

Faktorisierung

Wird die eingegebene Zahl als zerlegbar erkannt, so wird zuerst nach kleinen Primteilern bis 1 Million gesucht.

Die verbliebene Restzahl wird nun dem Pollardschen Verfahren unterzogen. Wird ein Teiler gefunden, so wird die Ausgangszahl durch diesen geteilt, und mit dem Ergebnis neu gerechnet, bis die Restzahl prim ist, d.h. die Zahl vollständig faktorisiert ist.

Wenn das Verfahren von Pollard nach einer festgelegten Anzahl von Pollard-Iterationen kein Ergebnis findet, wird eine Faktorisierung mit Hilfe elliptischer Kurven nach Lenstra durchgeführt. Hier werden nun die eingestellte Anzahl elliptischer Kurven ausgewertet.

Für größere Zahlen ab 50 Stellen nutzt man eine der schnellsten, heute bekannten Methode, die Zahlzerlegung mit Hilfe eines quadratischen Siebes.
Haben Sie den Punkt MPQS-Faktorisierung sofort bei weniger als xx Stellen verwenden markiert, wird dieses 4.Verfahren gestartet, wenn die verbleibende Zahl weniger als die eingegebene Stellenzahl hat. Ermittelt das Verfahren der elliptischen Kurven kein Ergebnis, wird automatisch zur Faktorisierung mit dem quadratischen Sieb umgeschaltet.

Mit den neuen Methoden der elliptischen Kurven und des quadratischen Siebes konnte auch die als Teiler der R74-Zahl auftretende zusammengesetzte Zahl
125339984708521865560332401639447 =
= 422650073734453 · 296557347313446299
in 0,08 Sekunden zerlegt werden. Das reine Verfahren nach Pollard schlug nach 80 Millionen Iterationsschritten fehl.

Ebenso gelang es alle Repetition-Unit-Zahlen bis R96 und die Mersenneschen Zahlen bis M292 zu faktorisieren.
Die Repetition-Unit-Zahlen R97, d.h. eine Zahl aus 97 Einsen bestehend, entzieht sich hier der Zerlegung. Sollten Sie allerdings viel Zeit haben, so wird auch für diese Zahl eine Lösung gefunden. Auf dem Testrechner wird eine theoretische Berechnungszeit von 48 Stunden vorhergesagt.

Besonders interessant ist auch, dass die 78stellige 257. Mersennesche Zahl
231584178474632390847141970017375815706539969331281128078915168015826259279871
in die drei Primfaktoren
gefundener Teiler         535006138814359
gefundener Teiler         1155685395246619182673033 (25)
gefundener Teiler         374550598501810936581776630096313181393 (39)
Zeit = 56 s
zerlegt werden konnte.
Gegenwärtig  kann damit jede Zahl bis 80 Stellen in vertretbarer Zeit in diesem Teilprogramm zerlegt werden.

Faktorisierung mit quadratischem Sieb

Als Einzelprogramm steht hier die Faktorisierung mit einem quadratischen Sieb zum Download bereit.