Mathematik: Faktorisierung großer Zahlen
Released by matroid on Sa. 15. März 2008 17:35:02 [Statistics]
Written by Kay_S - 18501 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Faktorisierungsverfahren

Bekannterweise ist das klassische Problem, die Primzahlen von den zusammengesetzten Zahlen zu unterscheiden, nach heutigem Kenntnisstand sehr effizient lösbar. Als viel schwieriger erweist es sich aber, die komplette Faktorzerlegung einer natürlichen Zahl anzugeben. Obwohl dieses Problem sehr alt und grundlegend ist, muss man tief in die mathematische Trickkiste greifen, um selbst Primfaktoren moderater Länge bestimmen zu können. Der Artikel beleuchtet klassische und aktuelle Verfahren zur Faktorisierung. Neben den Verfahren selbst stehen Laufzeitanalyse und Hinweise zur effizienten Realisierung auf dem Computer im Mittelpunkt. Am Ende soll auch eine Beispielimplementation einiger dieser Verfahren vorgestellt werden.

0. Überblick

Dass eine natürliche Zahl eine (bis auf die Reihenfolge der Faktoren) eindeutige Primfaktorzerlegung besitzt, hatte schon Euklid etwa 300 v. Chr. gezeigt. Lange Zeit haben sich die meisten Mathematiker auch mit diesem Wissen begnügt; die konkreten Faktoren zu bestimmen war meist die damit verbundene Arbeit nicht wert. Das änderte sich schlagartig Mitte der 60er Jahre des vorigen Jahrhunderts, als leistungsfähige Computer verfügbar wurden und - etwas später - das RSA-Kryptosystem erfunden wurde. Daraufhin wurde viel Energie in die Erforschung der Problematik und die Entwicklung "guter" Faktorisierungsalgorithmen gesteckt - mit mäßigem Erfolg. Bis heute ist es niemandem gelungen, das Faktorisierungsproblem als effizient lösbar nachzuweisen. Dennoch sollen einige der Ergebnisse bzw. Verfahren in den nachfolgenden Kapiteln besprochen werden:
1. Probedivision 2. Fermat-Faktorisierung 3. Lehman-Algorithmus 4. Pollard-Rho-Verfahren 5. (p-1)-Verfahren 6. Elliptische-Kurven-Methode 7. Quadratisches Sieb 8. Ein Faktorisierungs-Programm in C
Ohne Vollständigkeit zu garantieren sollte der Artikel insgesamt einen guten Überblick liefern.

1. Probedivision

Die Probedivision ist die naive Methode, Primfaktoren zu erhalten. Man fängt an, durch 2, 3, usw. zu dividieren, und schaut, ob die Division aufgeht. Wenn ja, hat man einen Primfaktor gefunden. Das Verfahren hat seine Berechtigung, da das Vorhandensein kleiner Faktoren sehr viel wahrscheinlicher ist als das großer; eine Division ist auch sehr schnell ausgeführt. Ist N die zu faktorisierende Zahl und gibt es einen Teiler a > \sqrt(N) von N, so ist der Komplementärteiler b = N/a kleiner als \sqrt(N). Es reicht also, die Probedivisionen bis \sqrt(N) auszuführen. \boxon\frameon\big\ Algorithmus (Probedivision)\normal 1. Eingabe: N 2. Für alle 2 <= p <= \sqrt(N): Falls p \| N: Abbruch 3. Ausgabe: p\boxoff\frameoff An dieser Stelle soll ausdrücklich darauf hingewiesen werden, dass man sich erst vergewissern sollte, ob N auch wirklich zusammengesetzt ist. Das ist leicht möglich \(z. B. mit dem Miller\-Rabin\-Test) und soll hier nicht weiter erläutert werden. Verbesserungen Eigentlich genügt es, nur Primzahlen p zu testen. Ist a = p*q zusammengesetzt, so testet man ja p bzw. q viel früher als a. Dazu müsste man vorher eine Primzahltabelle erstellen, was sich aber nicht immer lohnt. Man kann sich aber mit folgender Überlegung behelfen: Hat man bereits durch 2 getestet, so kann man sich alle anderen durch 2 teilbaren Zahlen sparen, indem man nur die ungeraden Zahlen testet. Will man auch den Vielfachen von 3 aus dem Weg gehen, so testet man nur alle zu 2*3 = 6 teilerfremden Zahlen \(welche von der Form 6k \pm 1 sind). Um zusätzlich die 5 zu berücksichtigen, testet man nur alle zu 30 teilerfremden Zahlen (diese sind von der Form 30k \pm 1, \pm 7, \pm 11, \pm 13). Das kann man zwar beliebig weitertreiben, wird aber schnell ziemlich mühsam. Mit der Probedivision kann man sehr schnell alle "Trivialteiler" erkennen. Bei einer Laufzeit von \Theta(p) für einen Primfaktor p ist sie aber ab einer gewissen Größe der Faktoren nicht mehr praktikabel.

2. Fermat-Faktorisierung

Eines der klassischen Verfahren hat Fermat 1643 in einem Brief erwähnt. Darin stellt er die zu zerlegende Zahl als Differenz zweier Quadrate dar. Dann gilt N = x^2 - y^2 = (x + y)(x - y) und man bekommt eine Faktorzerlegung von N. Ausgehend von der umgestellten Gleichung x^2 - N = y^2 kam Fermat auf die Idee zu prüfen, ob die Differenz x^2 - N \(für verschieden gewählte x) ein Quadrat darstellt. Die Wahrscheinlichkeit dafür ist am größten, wenn x^2 in der Nähe von N liegt. Das Verfahren definiert also eine Folge x_k mit x_0 := ceil(\sqrt(N)) und x_k := x_0 + k und testet, ob z_k := x_k^2 - N ein Quadrat ist. \boxon\frameon\big\ Algorithmus (Fermat\-Verfahren)\normal 1. Eingabe: N (ungerade) 2. Für x := ceil(\sqrt(N)) bis N/6: z := x^2 - N Falls z = y^2, y \in \IN: Abbruch 3. Ausgabe: (x - y)\boxoff\frameoff Beispiel Am Beispiel von N = 314731 soll das einmal demonstriert werden. Wir beginnen bei x_0 := ceil(sqrt(N)) = 562 und bekommen die folgenden Werte:
Bild
Bereits nach vier Iterationen haben wir ein Quadrat und bekommen die Zerlegung N = 566^2 - 75^2 = (566 - 75)(566 + 75) = 491 * 641. Man prüft leicht nach, dass es sich um Primfaktoren handelt. Verbesserungen Überlegen wir uns, wie wir dieses Verfahren effizient umsetzen können. Statt jedesmal eine Quadrierung durchzuführen nutzen wir die Beziehung x_(k+1)^2 = (x_k + 1)^2 = x_k^2 + 2x_k + 1, es folgt z_(k+1) = z_k + 2x_k + 1, was sich viel leichter berechnen lässt. Auch Wurzelziehen ist teuer; wir versuchen daher schon im Vorfeld zu entscheiden, ob z_k überhaupt ein Quadrat sein kann. Dazu bestimmen wir den Rest r \equiv z_k modulo einer geeigneten kleinen Zahl m. Ist r kein quadratischer Rest mod m, so kann z_k auch keine Quadratzahl sein. Für m = 10 gibt es nur die quadratischen Reste {0, 1, 4, 5, 6, 9}, die beiden ersten berechneten Werte für z_k scheiden also schon mal aus \(diese enden auf 3 und 8). Noch besser sieht es bei m = 16 aus, dort haben wir nur {0, 1, 4, 9} als mögliche Reste. Man kann also anhand der letzten vier Bit sofort 75% der Nichtquadrate identifizieren. Laufzeit Jetzt kann man sich fragen, ob der Fermat\-Algorithmus eigentlich alle Faktoren findet \- und wenn ja, wie lange er dafür braucht. Sei zunächst N ungerade und N = p*q (wobei p >= q). Dann gilt mit x := (p + q)/2 und y := (p - q)/2 die geforderte Eigenschaft N = x^2 - y^2. Da alle x getestet werden, werden p und q in jedem Fall gefunden. Weiterhin sieht man leicht, dass der Algorithmus versagt, falls N gerade und nicht durch 4 teilbar ist. Potenzen von 2 sollten also vorher herausdividiert werden. \boxon\frameon\stress\ Satz:\normal Ist N = p*q ungerade und \abs(p - q) <= c*wurzel(4, N) mit c > 0. Dann werden p und q in \Theta(c^2) Schritten gefunden.\boxon\frameoff Beweis: Sei o. B. d. A. p >= q und N = (x + y)(x - y) die gefundene Lösung \(d.h. y = (p - q)/2\.), welche in Schritt k gefunden wird. Wir benutzen die Ungleichungen x_0 <= \sqrt(N) + 1 \(also x_0^2 <= N + 2 \sqrt(N) + 1) und z_k = y^2 <= c^2/4 \sqrt(N) und die explizite Darstellung z_k = z_0 + 2kx_0 + k^2. Für k gilt dann k = \sqrt(x_0^2 + z_k - z_0) - x_0 <= \sqrt(N + 2 \sqrt(N) + 1 + c^2/4 \sqrt(N) - 1) - \sqrt(N) = \sqrt(N + (2 + c^2/4) \sqrt(N)) - \sqrt(N) = \sqrt(N)(\sqrt(1 + (8 + c^2)/(4 \sqrt(N))) - 1) <= \sqrt(N)(1 + (8 + c^2)/(8 \sqrt(N)) - 1) = 1 + c^2/8 \bigbox Wenn sich die Faktoren p und q also nur um wurzel(4, N) unterscheiden, werden sie quasi sofort gefunden. Desto weiter sie aber auseinanderliegen, desto schlechter wird das Verfahren. Im schlimmsten Fall werden N/6 Operationen gebraucht, weil erst dann ein Trivialfaktor wie 3 gefunden wird.

3. Lehman-Algorithmus

Eine interessante Kombination von Probedivision und Fermat\-Verfahren mit verbesserter Laufzeit wurde von R. S. Lehman [1] vorgestellt. Er benutzt den folgenden Satz: \boxon\frameon\stress\ Satz (von Lehman):\normal Ist N = p*q ungerade mit Primzahlen p, q und ist 1 <= r < \sqrt(N), wobei \sqrt(N/(r + 1)) <= p <= \sqrt(N), so gibt es natürliche Zahlen x, y und k mit den Eigenschaften 1. x^2 - y^2 = 4kN 2. x \equiv 1 (mod 2), falls k gerade und x \equiv k + N (mod 4), falls k ungerade 3. \sqrt(4kN) <= x <= \sqrt(4kN) + 1/(4(r + 1))*\sqrt(N/k) Ist N prim, gibt es solche Zahlen nicht.\boxon\frameoff Darauf aufbauend hat Lehman ein Verfahren zur Faktorzerlegung angegeben. Damit die Laufzeit möglichst klein wird und die Voraussetzungen des Satzes sicher erfüllt sind, muss r = wurzel(3, N) gewählt werden. Man macht zunächst eine Probedivision bis r. Findet sich kein Teiler \(wobei N aber in jedem Fall zusammengesetzt ist), so sind die Voraussetzungen des Satzes erfüllt. Man geht jetzt alle erdenklichen Paare (k, x) durch, die Punkt 3 des Satzes erfüllen \(wobei offensichtlich 1 <= k <= r) und prüft, ob x^2 - 4kN eine Quadratzahl (= y^2) ist. Wenn ja, so liefern ggT(x - y,N) und ggT(x + y,N) die gesuchten Faktoren p und q. \boxon\frameon\big\ Algorithmus (Lehman\-Verfahren)\normal 1. Eingabe: N 2. Probedivision bis wurzel(3, N); bei Erfolg: Ausgabe p 3. Für k := 1 bis wurzel(3, N): Für x := \sqrt(4kN) bis \sqrt(4kN) + wurzel(6, N)/(4 \sqrt(k)) z := x^2 - 4kN Falls z = y^2, y \in \IN: Abbruch 4. Ausgabe: ggT(x - y,N)\boxoff\frameoff Laufzeit Schauen wir uns die Laufzeit an: Die Probedivision kostet \Theta(wurzel(3, N)) Operationen. Die beiden geschachtelten Schleifen sehen erstmal sehr aufwändig aus, der Aufwand ist aber mit \Theta(sum(\wurzel(6, N)/(4 \sqrt(k)), k=1, wurzel(3, N))) = \Theta(int(\wurzel(6, N)/(4 \sqrt(k)), k, 1, wurzel(3, N))) = \Theta(wurzel(3, N)) erforderlichen Operationen vergleichbar mit der Probedivision. Damit haben wir ein Verfahren kennengelernt, das asymptotisch besser als die Probedivision ist. Dass das überhaupt möglich ist, liegt ja nicht auf der Hand!

4. Pollard-Rho-Verfahren

Mit dem folgenden, von John M. Pollard 1975 vorgestellten Verfahren können wir die Laufzeit, einen Primfaktor p zu finden, auf \Theta(\sqrt(p)) herunterschrauben. Das gelingt uns aber nur unter Aufgabe der Erfolgsgarantie, die wir ja bei den bisherigen Verfahren hatten. Es handelt sich um eine Monte\-Carlo\-Methode, bei der der Zufall mit von der Partie ist. Eine Geburtstagsfolge Das Verfahren beruht auf der Ausnutzung des Geburtstagsparadoxons. Bei diesem Problem geht es eigentlich um die Frage, wie groß eine Gruppe Personen sein muss, um mit mindestens 50%iger Wahrscheinlichkeit zwei mit demselben Geburtsdatum darunter zu haben \(Lösung: 23). Allgemeiner haben wir eine Urne mit p Kugeln und fragen nach der mittleren Anzahl Ziehungen mit Zurücklegen, bis die erste Wiederholung auftaucht. Es stellt sich heraus, dass wir dafür nur ungefähr \sqrt(p) Versuche benötigen. Wie kann man sich das überlegen? Die Chance auf eine Wiederholung steigt linear mit der Zahl der Versuche, die Gesamtchance damit quadratisch. Das Faktorisierungsverfahren definiert nun eine Zufallszahlenfolge a_k modulo N. Ist p ein Teiler von N, so können wir also davon ausgehen, dass etwa unter den ersten \sqrt(p) Folgengliedern eine Wiederholung der Folge modulo p auftritt. In diesem Fall hätten wir ein Paar (a_i, a_j) mit der Eigenschaft a_i \equiv a_j (mod p). Wenn wir dieses Paar fänden, könnten wir p = ggT(a_i - a_j,N) berechnen \(natürlich dürfen Trivialfälle wie a_i \equiv a_j (mod N) nicht eintreten). Floyd's Zyklenalgorithmus Das Problem liegt im Finden, denn wir können schlecht alle Paare testen \(das sind immerhin \approx p Stück). Man kann dieses Problem aber dennoch lösen: Dazu wählen wir keine "echte" Zufallsfolge a_k, sondern eine Pseudozufallsfolge mit einer deterministischen Berechnungsvorschrift a_(k+1) = f(a_k). Dadurch ist gewährleistet, dass a_k mod p in eine Periode eintritt, falls sich ein Element wiederholt. Die Funktion f sollte einfach gehalten sein, aber dennoch hinreichend "zufällige" Zahlen erzeugen. Bewährt hat sich a_(k+1) = f(a_k) = a_k^2 + c (mod N) c \notin {-2, 0} Nach Durchlauf einer Vorperiode der Länge m kommt die Folge a_k mod p in eine Periode der Länge l \approx \sqrt(p); man kann sich leicht davon überzeugen, dass das bei einer linearen Funktion f nicht der Fall ist. Anschaulich ergibt sich eine Schleife, die an den griechischen Buchstaben \rho erinnert \(der auch der Namensgeber der Methode ist):
Bild
Die Existenz einer Periode bewirkt, dass wir mit einem speziellen Algorithmus das fragliche Paar (a_i, a_j) finden können, ohne alle Paare zu testen. Wir können uns nämlich ohne Mühe davon überzeugen, dass der folgende Satz gilt: \boxon\frameon\stress\ Satz: (von Floyd)\normal Für eine periodische Folge a_k mod p mit Vorperiode m und Periode l gilt a_i \equiv a_j (mod p) => i \equiv j (mod l)\boxoff\frameoff Die Differenz j - i ist dabei entweder genau l oder ein kleines Vielfaches von l, da man annehmen kann, dass die Vorperiode nicht viel länger ist als die Periode. Der Zyklenalgorithmus von Floyd macht sich diese Eigenschaft zu Nutze, indem er nur die Paare (a_k, a_(2k)) für aufsteigende k testet. Denn irgendwann ist 2k - k = k das entsprechende Vielfache von l. Wir können natürlich nicht die Paare (a_0, a_k) testen, da a_0 mit hoher Wahrscheinlichkeit in der Vorperiode liegt. Wegen l \approx \sqrt(p) benötigen wir für das Finden also nur \Theta(\sqrt(p)) Schritte. \boxon\frameon\big\ Algorithmus (Pollard\-Rho\-Verfahren)\normal 1. Eingabe: N 2. Wähle 0 < x = y < N und c \notin {-2, 0}, p := 1 3. Solange (p = 1): x = x^2 + c (mod N) y = (y^2 + c)^2 + c (mod N) p = ggT(x - y, N) 4. Ausgabe: p\boxoff\frameoff \(Im Algorithmus ist a_k = x und a_(2k) = y.) Beispiel Rechnen wir dazu ein Beispiel. Gegeben sei N = 222473; unsere Folge beginnt mit a_0 := 1, als Rekursion benutzen wir a_(k+1) = a_k^2 + 1 (mit c = 1). Die einzelnen Rechenschritte lassen sich in folgender Tabelle ablesen:
Bild
Wie wir sehen, erhalten wir nach 12 Iterationen den Faktor 379 und damit die Zerlegung N = 379 * 587. Verbesserungen Natürlich bräuchte man die Werte für a_k nicht nochmals neu berechnen, da man diese ja schon einmal vorher \(für a_(2k)\.) erzeugt hat. Man kann das Verfahren also etwas schneller machen, wenn man die a_k speichert. Dann geht aber einer der Vorteile des Verfahrens \- geringer Platzbedarf \- verloren. Nachbessern kann man aber noch an einem anderen Punkt: Statt nach jeder Iteration den ggT zu berechnen, können wir das Produkt P(k_0) := produkt((a_(2k) - a_k),k=k_0,k_0+n) (mod N) der Werte aus n Iterationen bilden \(z. B. n = 50) und erst danach den ggT(P(k_0),N) bestimmen. Für die ggT\-Berechnung muss extra der Euklidische Algorithmus angeworfen werden, der hier mit Abstand den größten Rechenaufwand verursacht. Ein eventueller Faktor p geht dadurch nicht verloren. Allerdings steigt die Gefahr, dass auch ein zweiter Faktor q sich im Produkt wiederfindet. Eine weitere Verbesserung wurde von Richard P. Brent vorgeschlagen. Diese besteht darin, den Algorithmus von Floyd durch einen etwas schnelleren zu ersetzen \- der Unterschied ist aber marginal. Laufzeit Wie bereits oben erklärt, haben wir eine heuristische Laufzeit von \Theta(\sqrt(p)). Wer das immer noch nicht glaubt, der schaue sich folgende Rechnung an: a_(2k) - a_k = (a_(2k-1)^2 + c) - (a_(k-1)^2 + c) | | = (a_(2k-1)^2 - a_(k-1)^2) | | = (a_(2k-1) + a_(k-1)) * (a_(2k-1) - a_(k-1)) | | = (a_(2k-1) + a_(k-1)) * ((a_(2k-2)^2 + c) - (a_(k-2)^2 + c)) | | = (a_(2k-1) + a_(k-1)) * (a_(2k-2)^2 - a_(k-2)^2) | | = (a_(2k-1) + a_(k-1)) * (a_(2k-2) + a_(k-2)) * (a_(2k-2) - a_(k-2)) | | = ... | | = (a_(2k-1) + a_(k-1)) * (a_(2k-2) + a_(k-2)) * ... * (a_k + a_0) * (a_k - a_0) | | = (a_k - a_0) * produkt((a_(k+i) + a_i),i=0,k-1) Die Iterierte a_(2k) - a_k ist also ein Produkt aus k Faktoren modulo N \(bzw. p). Taucht in nur einem dieser Faktoren unser p auf, so finden wir p durch Berechnung von ggT(a_(2k) - a_k,N). Der Trick besteht also darin, pro Iteration nicht nur einen potentiellen Faktor auf Teilbarkeit zu testen \(wie bei der Probedivision), sondern gleich mehrere parallel. Nach k Iterationen haben wir ungefähr k^2 Faktoren getestet. Die genaue Anzahl der erforderlichen Iterationen kann man natürlich nicht vorhersehen. Je nach Wahl von a_0 und c kommt man mal schneller, mal langsamer zum Ziel. Es kann auch vorkommen, dass von zwei Primfaktoren der größere zuerst gefunden wird. Ein weiterer \(unwahrscheinlicher) Fall, der eintreten kann ist, dass ggT(a_(2k) - a_k,N) = N zurückgegeben wird. Das ist dann der Fall, falls sich modulo aller Primteiler gleichzeitig eine Periode bildet.

5. (p-1)-Verfahren

Das (p-1)\-Verfahren von Pollard nutzt die Struktur der Gruppe \IF_p^\* \(der Menge {1, 2, ..., p-1} mit der Multiplikation modulo p) aus. Es basiert auf den bekannten Sätzen von Fermat und Lagrange. \boxon\frameon\stress\ Satz \(von Fermat):\normal Ist p eine Primzahl und a \el\ \IN nicht durch p teilbar, dann gilt a^(p-1) \equiv 1 (mod p)\boxoff\frameoff Beweis: Der Standardbeweis läuft so: Da a und p teilerfremd sind, durchlaufen alle Vielfachen von a, also 1a, 2a, ..., (p-1)a die ganze Gruppe \IF_p^\*. Deswegen gilt 1 * 2 * ... * (p-1) \equiv 1a * 2a * ... * (p-1)a (mod p). Durch Anwenden der Kürzungsregel bekommen wir die Behauptung a^(p-1) \equiv 1 (mod p). \bigbox Hier und in den beiden folgenden Kapiteln wird noch der Primzahlsatz benötigt, weswegen wir ihn hier noch schnell einschieben. \boxon\frameon\stress\ Satz \(Primzahlsatz):\normal Gegeben ist die Primzahlfunktion \pi(x) := abs({p Primzahl, p <= x}). Dann gilt die Asymptotik lim(x->\inf,\pi(x)/(x/ln(x))) = 1.\boxoff\frameoff Das heißt, die Anzahl der Primzahlen kleiner oder gleich x kann durch x/ln(x) abgeschätzt werden. Für die nachfolgenden Ausführungen brauchen wir noch den Begriff der Glattheit: \boxon\frameon\stress\ Definition \(glatt, potenzglatt):\normal Sind N, B natürliche Zahlen, so heißt N B\-glatt, falls alle Primteiler von N nicht größer sind als B. N heißt potenzglatt, wenn das auch für alle Primzahlpotenzen gilt.\boxoff\frameoff 175 \(= 5^2 * 7) wäre also 7\-glatt, 25\-potenzglatt, aber nicht 7\-potenzglatt. Ist jetzt p eine Primzahl und p-1 = p_1 * p_2 * ... * p_k die Primfaktorzerlegung von p-1 in absteigender Ordnung (also p_1 >= p_2 >= ... >= p_k) und B eine natürliche Zahl, für die p-1 B\-potenzglatt ist (daraus folgt schon mal B >= p_1), dann gilt für jedes m \el\ \IN, das durch alle Zahlen <= B teilbar ist p-1 \| m und a^m \equiv 1 (mod p) Falls die Kongruenz a^m \equiv 1 (mod p) für einen Primteiler p von N gilt \(und für keinen anderen!), so bekommen wir p durch Berechnung von p = ggT(a^m - 1,N). Abgesehen von dem Problem, dass wir B >= p_1 wählen müssen, müssen wir sicherstellen, dass p-1 ein Teiler von m ist. Eine einfache Wahl von m wäre m = B!. Bei "normalen" Zahlen p-1 reicht es aber, wenn m alle Primzahlen <= p_1 enthält; die großen nur einmal, sehr kleine \(z. B. < 50) auch mehrfach. Jetzt wird sich mancher fragen, ob a^m - 1 (mod N) überhaupt effizient berechenbar ist. Dazu betrachten wir die Aufgabe, b \equiv a^m (mod N) zu bestimmen. m besitzt eine eindeutige Binärdarstellung m = sum(2^i,i \el\ I) \(mit einer Indexmenge I). Dann gilt: b \equiv a^m \equiv a^(sum(2^i,i \el\ I)) \equiv produkt(a^2^i,i \el\ I) (mod N) Die Werte a^2^i erhält man einfach durch fortgesetztes Quadrieren modulo N. Die Zahl der benötigten Quadrierungen entspricht der Anzahl der Bits von m und wächst demzufolge logarithmisch mit m. Es geht also sehr effizient \(diese Potenzierungsmethode wird auch Square & Multiply genannt). Der Algorithmus berechnet nun nicht a^m - 1 (mod N) an einem Stück, sondern schrittweise a_0 := a, a_(k+1) := a_k^q_k (mod N) mit allen in m enthaltenen Primteilern q_k. Zwischendurch wird sporadisch getestet, ob ggT(a_k - 1,N) > 1 ist. Wurde B hinreichend groß gewählt, dann bekommen wir den Primfaktor p. \boxon\frameon\big\ Algorithmus \((p-1)\-Verfahren, Version 1)\normal 1. Eingabe: N 2. Wähle 1 < a < N-1, B \el\ \IN 3. Für alle Primzahlen q <= B (kleine q mehrfach): a := a^q (mod N) p := ggT(a - 1,N) Falls p \| N: Abbruch 4. Ausgabe: p\boxoff\frameoff \(m wäre hier also das Produkt der q aus Schritt 3). Beispiel Diesmal ist N = 90044497 zu zerlegen. Wir machen einen einfachen Test mit B = 50; begonnen wird mit a_0 = 2. Potenziert wird mit allen Primzahlen <= 50, mit den Primzahlen 2, 3 dreifach, mit 5 und 7 zweifach. Es ergeben sich folgende Werte:
Bild
Daraus erhalten wir N = 5743*15679. Schaut man sich die Zerlegung von p-1 an, so ergibt sich p-1 = 5742 = 2 * 3 * 3 * 11 * 29. Insbesondere sehen wir, dass das mehrfache Vorkommen kleinerer Primzahlen zu berücksichtigen ist. Für den Komplementärteiler gilt 15678 = 2 * 3 * 3 * 13 * 67, dieser ist also weniger glatt und wird erst ein paar Iterationen später gefunden. Eine schnellere Version Nach dem Satz von Lagrange ist die Ordnung jeder Untergruppe von \IF_p^\* ein Teiler von p-1. Potenzieren wir eine der Iterierten a_k mit einem Teiler von p-1, so gelangt man in eine kleinere Untergruppe von \IF_p^\* \(wodurch sich die Chance erhöht, dass man später a_k \equiv 1 (mod p) erhält). Bleibt nur ein Primteiler übrig, d. h. hat man b := a^(p_2 * ... * p_k) berechnet, so braucht man nicht mehr mit allen weiteren Primzahlen zu potenzieren. Es reicht, wenn wir b^(p_1) finden. Das können wir viel einfacher erreichen, indem wir aufsteigend b^(q_i) mit Primzahlen q_i berechnen bis q_i = p_1 ist. Wegen b^(q_(i+1)) = b^(q_i + d_i) = b^(q_i) * b^(d_i) brauchen wir dafür nur die zu den entsprechenden Primzahldifferenzen d_i zugehörigen Werte b^(d_i) ranzumultiplizieren. Die Werte für b^(d_i) kann man vorberechnen und abspeichern. Der resultierende Speicheraufwand ist gering, da die Abstände d_i nach dem Primzahlsatz von der Größenordnung log(p_i) sind. Die Berechnungen sind dann insgesamt deutlich schneller. Der modifizierte Algorithmus sieht also so aus: Wir definieren zwei Schranken B_1 und B_2 \(wobei B_1 << B_2) und wenden Version 1 des Verfahrens mit B_1 als Schranke an. Danach haben wir ein Element b \el\ \IF_p^\* bekommen und berechnen weiter alle Potenzen b^(q_i) für Primzahlen B_1 < q_i <= B_2. Da diese Berechnungen deutlich schneller vonstatten gehen, kann B_2 sehr viel größer als B_1 gewählt werden. \boxon\frameon\big\ Algorithmus \((p-1)-Verfahren, Version 2)\normal 1. Eingabe: N 2. Wähle 1 < a < N-1, B_1, B_2 \el\ \IN, B_1 < B_2 3. Phase 1: Für alle Primzahlen q <= B_1 (kleine q mehrfach): a := a^q (mod N) p := ggT(a - 1,N) Falls p \| N: Abbruch 4. q_0 := kleinste Primzahl > B_1, b := a^(q_0) (mod N) 5. Phase 2: Für alle Primzahlen q_0 < q_k <= B_2 (k = 1, 2, ...) b := b * a^(q_k - q_(k-1)) (mod N) p := ggT(b - 1,N) Falls p \| N: Abbruch 6. Ausgabe: p\boxoff\frameoff [Die Werte a^2, a^4, ..., die a^(q_k - q_(k-1)) annehmen kann, werden vor Schritt 5 berechnet und gespeichert.] Der Wermutstropfen: Neben der Bedingung aus Version 1 (p_1 <= B_2) muss zusätzlich p_2 <= B_1 gelten, da sonst der Algorithmus versagt. Untersuchungen haben aber ergeben, dass im Normalfall p_2 << p_1 gilt, so dass es i. a. keine Probleme geben sollte. Weitere Verbesserungen Ähnlich wie beim Rho\-Verfahren sind wir bestrebt, die Zahl der ggT-Berechnungen gering zu halten. Daher werden zunächst n Stück \(z. B. n = 100) der erzeugten Werte b-1 modulo N aufmultipliziert und erst dann der ggT gebildet. Pollard hat in seiner Originalarbeit eine Methode angegeben, Phase 2 spürbar zu beschleunigen. Die Idee ist folgende: Die gesuchte Primzahl p_1 lässt sich eindeutig darstellen als p_1 = vw - u, wenn w := ceil(sqrt(B_2)) und u < w, v <= w sind. Ist jetzt p ein Teiler von b^(p_1)-1, so auch von b^vw-b^u. Pollard definiert nun ein Polynom h(x) = produkt((x - b^u),uLaufzeit Wie man sieht, werden \Theta(p_1) Operationen benötigt. Die Größe des größten Primfaktors von p-1 entscheidet also über die Laufzeit. Da man den noch nicht mal kennt, ist das Verfahren wiederum ein Glücksspiel. Um wenigstens herauszufinden, was wir so im Mittel zu erwarten haben, benutzen wir den folgenden Satz: \boxon\frameon\stress\ Satz (von Hardy\/Ramanujan):\normal Ist \Omega(N) die Anzahl aller Primteiler von N, dann gilt im Mittel die Abschätzung \Omega(N) \approx log log(N).\boxoff\frameoff Für p-1 = p_1 * ... * p_k können wir den Ansatz k-1 \approx log log(p/p_1) = log(log(p) - log(p_1)) = log(log(p) * (1 - log(p_1)/log(p))) = log log(p) + log((p_1)/log(p)) \approx k + log((p_1)/log(p)) machen. Als Abschätzung für p_1 bekommen wir log(p_1) \approx (1 - 1/e)log(p) \approx 0.632 log(p). Die Laufzeit hat dann also einen "Erwartungswert" von \Theta(p^0.632). Die Varianz ist aber sehr hoch, so dass man mit diesem Verfahren auch recht große Faktoren finden kann \(auch wenn man in 90% der Fälle Pech hat). Darüberhinaus gibt es noch ein Verfahren \(von H. C. Williams), das sich die Glattheit von p+1 zu Nutze macht, was die Erfolgsaussichten erhöht.

6. Elliptische-Kurven-Methode

Wie gerade gesehen hat das (p-1)\-Verfahren den unschönen Nachteil, dass die Laufzeit von der Glattheit der Gruppenordnung \- auf die man keinerlei Einfluss hat \- abhängt. Das nachfolgend vorgestellte \(1985 von H. W. Lenstra jr. erfundene) Verfahren funktioniert nach demselben Prinzip, bietet aber die Möglichkeit der Einflussnahme. Die Chance, einen Primfaktor p zu finden, kann dadurch erhöht werden. Wir brauchen dazu den Begriff der elliptischen Kurve, den wir für unsere Zwecke etwas einschränken. \boxon\frameon\stress\ Definition \(Elliptische Kurve):\normal Seien a, b \el\ \IK für einen Körper \IK und x^3 + ax + b ein Polynom ohne mehrfache Nullstelle. Die Menge \IE der Punkte (x, y), die die Gleichung y^2 = x^3 + ax + b erfüllt, zuzüglich einem Element O heißt elliptische Kurve über \IK.\boxoff\frameoff Eine typische Kurve über \IK = \IR zeigt die untenstehende Abbildung.
Bild
Wir interessieren uns hier aber für den Restklassenkörper \IF_p für eine Primzahl p. Elliptische Kurven über \IF_p spielen auch eine wichtige Rolle in der Kryptographie. Die für uns wesentliche Eigenschaft ist die Tatsache, dass eine solche Kurve eine abelsche Gruppe darstellt. Punkte P, Q auf einer elliptischen Kurve lassen sich beliebig addieren bzw. invertieren, wobei der in der Definition erwähnte Punkt O die Rolle des neutralen Elementes übernimmt. Im einzelnen gelten für zwei Punkte P = (x_1, y_1), Q = (x_2, y_2) und deren Summe P + Q = (x_3, y_3) folgende Rechenregeln: 1. Invertierung: -P = (x_1, -y_1) und -O = O. Aus Q = -P folgt P + Q = O. 2. Addition: Es gilt x_3 = m^2 - x_1 - x_2 bzw. y_3 = -y_1 + m(x_1 - x_3), wobei m = cases((y_2 - y_1)/(x_2 - x_1), wenn P != Q;(3x_1^2+a)/(2y_1), wenn P = Q) Wie in jeder Gruppe ist die Ordnung ord(P) eines Punktes P \el\ \IE das kleinste m \el\ \IN, für das m*P = O ist; wir haben ja hier eine additiv geschriebene Gruppe vor uns. ord(\IE) entspricht dabei der Anzahl aller Punkte auf \IE. Es gilt der folgende wichtige Satz: \boxon\frameon\stress\ Satz \(von Hasse):\normal Sei \IE eine elliptische Kurve über \IF_p. Dann gilt für die Ordnung die Schranke abs(ord(\IE) - p - 1) < 2 \sqrt(p).\frameoff Das bedeutet, dass bei zufälliger Wahl der Kurvenparameter a und b die Gruppenordnung innerhalb eines Intervalls um p variiert. Man kann ungefähr von einer Gleichverteilung ausgehen; an den Rändern des Hasse\-Intervalls scheint die Dichte etwas geringer zu sein. Was hat das alles nun mit dem Faktorisierungsproblem zu tun? Gegeben sei wieder eine natürliche Zahl N und ein zu findener Primfaktor p von N. Wir würden nun gerne Punktadditionen auf einer elliptischen Kurve \IE über \IF_p anstellen. Da wir p leider nicht kennen, werden wir die oben genannten Operationen \(Addition, Multiplikation, Invertierung der x\/y\-Werte) modulo N ausführen. Da N ein Vielfaches von p ist, sind diese konform zu den jeweiligen Berechnungen modulo p. Unser Ziel ist es, eine Addition P + Q = O herbeizuführen. Ist P = (x_1, y_1) und Q = (x_2, y_2), so folgt P = -Q und damit \ll(1)x_1 == x_2 (mod p) \ll(2)y_1 == -y_2 (mod p) Wollten wir nun die Punkte P und Q addieren, so müssten wir nach den obigen Rechenregeln die Inversen (x_2 - x_1)^(-1) (mod N) und (im Falle P = Q) (2 y_1)^(-1) (mod N) bilden. Aufgrund der Kongruenzen \ref(1) und \ref(2) existieren die Inversen nicht und wir bekommen durch Berechnung von ggT(x_2 - x_1,N) und ggT(2y_1,N) mit hoher Wahrscheinlichkeit unseren Primfaktor p. Das funktioniert natürlich nicht, wenn die Kongruenzen \ref(1) und \ref(2) auch modulo anderer Primfaktoren q von N gelten. Um die gewünschte Addition zu bekommen, bedienen wir uns derselben Methodik wie das (p-1)\-Verfahren. Dort sind wir von einem Element a \el\ \IF_p^\* und einem geeigneten m \el\ \IN ausgegangen. War ord(a) \| m, so galt a^m == 1 (mod p), und wir hatten unser Ziel erreicht. Analog berechnen wir nun das Vielfache m*P. Ist ord(P) \| m, so gilt m*P = O. Das Vielfache m*P berechnen wir mit dem bereits vorgestellten Square & Multiply \- Verfahren, nur auf eine additive Gruppe angewandt \(es müsste demzufolge "Double & Add" heißen). Bis hierhin haben wir gegenüber dem (p-1)\-Verfahren nichts gewonnen. Ist aber nun m*P != O, so müssen wir nicht das Handtuch werfen, sondern können durch Variation der Kurvenparameter a und b immer wieder neue Kurven erzeugen. Da deren Ordnung einen Zufallswert im Hasse\-Intervall annimmt, können wir irgendwann doch noch Glück haben und es gilt ord(P)\|m. Mit dem Unterschied, dass wir auf einer anderen Gruppe arbeiten, entspricht das Vorgehen also genau dem des (p-1)\-Verfahrens. Daher wird im Folgenden gleich die erweiterte Fassung angegeben. \boxon\frameon\big\ Algorithmus (ECM)\normal 1. Eingabe: N 2. Wähl' eine elliptische Kurve \IE und einen Punkt P \el\ \IE; ebenfalls Schranken B_1, B_2 \el\ \IN, B_1 < B_2 3. Phase 1: Für alle Primzahlen q <= B_1 \(kleine q mehrfach): P := q*P Falls dabei eine Addition \(bzw. Verdopplung) nicht möglich ist: p = ggT(x_2 - x_1,N) (bzw. p = ggT(2y_1,N)) Abbruch 4. q_0 := kleinste Primzahl > B_1, Q := q_0*P 5. Phase 2: Für alle Primzahlen q_0 < q_k <= B_2 (k = 1, 2, ...) Q := Q + (q_k - q_(k-1))*P Falls dabei eine Addition \(bzw. Verdopplung) nicht möglich ist: p = ggT(x_2 - x_1,N) (bzw. p = ggT(2y_1,N)) Abbruch 6. Bei Misserfolg: Gehe zu 2. 7. Ausgabe: p\boxoff\frameoff [Vor Schritt 5 werden die möglichen Werte von (q_k - q_(k-1))*P vorberechnet und gespeichert.] Analog zum (p-1)\-Verfahren gilt auch hier: Ist ord(P) = p_1 * ... * p_k die Primfaktorzerlegung der Ordnung des Startpunktes (wobei p_1 >= p_2 >= ... >= p_k), so haben wir nur dann Erfolg, falls p_1 <= B_2 und p_2 <= B_1 ist. Ein \(kleiner) Vorteil ergibt sich hier noch aus der Tatsache, dass wir auf verschiedenen elliptischen Kurven parallel rechnen; mit jedem weiteren Primfaktor q von N korrespondiert ja eine entsprechende Kurve. Die Erfolgsaussichten werden aber im Wesentlichen durch den kleinsten Primfaktor bestimmt, sodass dieser Vorteil eher vernachlässigbar ist. Beispiel Versuchen wir das an einem Beispiel nachzuvollziehen. Die Eingabezahl ist N = 373935877613. Als elliptische Kurve wählen wir \IE: y^2 = x^3 + 11x - 11 und als Startpunkt P = (1, 1) \el\ \IE. Aus Gründen der Einfachheit verzichten wir auf die 2. Phase und wählen nur die Schranke B_1 = 15. Eine geeignete Zahl, die alle Primzahlen <= B_1 als Teiler enthält, ist z. B. m = 360360 = 2^3 * 3^2 * 5 * 7 * 11 * 13. Für das Double & Add \- Verfahren müssen wir m als Summe von Zweierpotenzen darstellen, d. h. m = 2^3 + 2^5 + 2^7 + 2^8 + ... + 2^14 + 2^16 + 2^18. Um uns unnötige Additionen zu ersparen, nehmen wir die kürzere Darstellung m = 2^3 + 2^5 - 2^7 + 2^15 + 2^16 + 2^18. Durch sukzessive Punktverdopplung erhalten wir nun 2^1 P = (47, 373935877290) 2^2 P = (227972965300, 183442291117) 2^3 P = (61805727327, 110535328079) ... 2^17 P = (280318713435, 342677737184) 2^18 P = (268323296538, 16670570674) Nun sind wir in der Lage, m*P durch Addition der entsprechenden Zweierpotenzen zu bestimmen: 2^3 P + 2^5 P = (70097302030, 311003332604) 2^3 P + 2^5 P - 2^7 P = (34669084331, 321123021245) 2^3 P + 2^5 P - 2^7 P + 2^15 P = (317161257334, 188842975469) 2^3 P + 2^5 P - 2^7 P + 2^15 P + 2^16 P = (120533742333, 164980145780) Nun müssen wir noch 2^18 P addieren und stellen fest, dass wir die Punktaddition (120533742333, 164980145780) + (268323296538, 16670570674) nicht ausführen können, da 268323296538 - 120533742333 = 147789554205 modulo N nicht invertierbar ist. Wir bekommen mit p = ggT(147789554205,N) = 157559 also einen Primfaktor von N. Für die Kurve \IE über \IF_(157559) gilt ord(P) = 182 = 2 * 7 * 13 und für die Gruppenordnung ord(\IE) = 157976 = 2^3 * 7^2 * 13 * 31. Diese lässt sich übrigens effizient mit Schoof's Algorithmus bestimmen. Das Beispiel zeigt auch gut, dass für den Erfolg die Ordnung des Startpunktes \(und nicht der Gruppe) entscheidend ist. Erweiterungen / Verbesserungen Ein großer Vorteil dieser Methode ist ihre uneingeschränkte Parallelisierbarkeit. Sämtliche Kurven sind voneinander unabhängig, so dass man die Berechnungen entsprechend verteilen kann. Es hat sich herausgestellt, dass man B_1 \/ B_2 so wählen sollte, dass sich ein Verhältnis von etwa 2:1 zwischen den Laufzeiten von Phase 1 bzw. 2 ergibt. Des weiteren gibt es noch einige Tricks, mit denen man die Effizienz noch etwas weiter steigern kann. Im folgenden eine Auswahl: 1) Einsparung von Punktadditionen In Phase 2 berechnen wir aufsteigend Punkte q*P für alle Primzahlen q im Intervall \(B_1, B_2]. Das kostet etwa B_2 \/ ln(B_2) Punktadditionen. Punktadditionen sind sehr teuer, da sie eine modulare Invertierung beinhalten \(dazu muss man den Erweiterten Euklidischen Algorithmus aufrufen). Man kann die Zahl der Additionen aber mit folgendem Trick auf etwa sqrt(B_2) verringern: Gegeben sei ein w \el\ \IN. Mit natürlichen Zahlen u <= w und v ergibt sich die \(eindeutige) Darstellung q = vw - u q*P = vw*P - u*P Fixiert man jetzt w in der Größenordnung sqrt(B_2), so gilt ebenfalls u, v \approx sqrt(B_2). Wir können jetzt die Werte vw*P und u*P berechnen und speichern, was 2 sqrt(B_2) Punktadditionen kostet. Statt nun die Differenzen vw*P - u*P auszurechnen, bestimmen wir nur den ggT(x_2 - x_1,N) der x\-Koordinaten von vw*P bzw. u*P und schauen, ob wir den gesuchten Faktor p bekommen. Weiter kann man Rechenzeit sparen, wenn man mehrere Werte (x_2 - x_1) vor der ggT\-Bildung aufmultipliziert. 2) Einsparung von Invertierungen Unter Verwendung einer anderen Kurvenparametrisierung kann man sogar ganz auf die Invertierungen verzichten. Die von uns eingeführten Kurven haben die Form \IE: y^2 = x^3 + ax + b, welche auch als Weierstrass\-Parametrisierung bekannt ist. Eine Kurve der Form \IE: by^2*z = x^3 + ax^2*z + x*z^2 mit Kurvenpunkten (x, y, z) liegt in der sog. Montgomery\-Parametrisierung vor. Eine Addition von Punkten dieser Form kommt ohne Invertierung aus; sie wird gerne für Phase 1 verwendet. Details zu dieser Parametrisierung kann man in [3] nachlesen. 3) Erhöhung der Glattheit der Gruppenordnung Man kann dafür sorgen, dass bei geeigneter Wahl der Kurvenparameter gewährleistet ist, dass die Ordnung ord(\IE) immer durch bestimmte \(kleine) Zahlen teilbar ist. Man kann damit also "künstlich" die Glattheit der Ordnung erhöhen. Besorgen tut dies ein sogenannter Kurvengenerator. Ein solcher liefert zu einem Zufallszahlenwert \sigma \el\ \IZ Kurvenparameter a, b für eine elliptische Kurve \IE mit besagter Eigenschaft. Daneben wird noch ein gültiger Startpunkt P \el\ \IE generiert. Als Beispiel wird kurz ein Generator für eine Kurve \IE in der oben genannten Montgomeryform angegeben. Sei \sigma \el\ \IZ zufällig gewählt. Dann bekommen wir mit u := 6\sigma/(\sigma^2 + 6) (mod N) a := (-3u^4 - 6u^2 + 1)/(4u^3) (mod N) P := (3u/4,~,1) (mod N) den Parameter a und einen Kurvenpunkt P auf \IE, wobei ord(\IE) immer durch 12 teilbar ist. Der Parameter b wird \(analog zur Weierstrassform) für Punktadditionen in Montgomeryform nicht benötigt \(ebenso kann man auf die Berechnung der y\-Koordinaten verzichten). Noch andere Erweiterungen werden in [3] beschrieben. Laufzeit Die Laufzeit hängt entscheidend davon ab, wieviele Kurven wir durchprobieren müssen, bis ord(P) die erforderliche Glattheitseigenschaft erfüllt. Wenn wir einerseits die Schranken B_1 \/ B_2 kleiner wählen, so sind wir mit der Berechnung einer Kurve schneller fertig und können somit mehr Kurven testen. Andererseits könnten wir sie größer wählen, um die Wahrscheinlichkeit für die Glattheit zu erhöhen. Für eine Antwort brauchen wir eine Aussage über die Häufigkeit glatter Zahlen. \boxon\frameon\stress\ Satz \(Canfield, Erdös, Pomerance):\normal Für die "Glattheitsfunktion" \psi(x,y) := abs({n \el\ \IN: n <= x, n besitzt keinen Primteiler > y}) gilt \psi(x,y) = x*u^(-u(1 + o(1))), wobei u := ln(x)/ln(y) .\boxoff\frameoff In Kurzform: Die Wahrscheinlichkeit, dass eine zufällig gewählte Zahl n <= x y\-glatt ist, beträgt etwa u^(-u). Für uns bedeutet das, dass wir ungefähr u^u Kurven zu testen haben, um einen Primteiler p zu finden, wobei hier u := ln(p)/ln(B_2) ist \(man kann u als das Längenverhältnis der Zahlen p und B_2 auffassen). Da die Double & Add \- Methode pro Kurve etwa B_2 Operationen benötigt, können wir eine Gesamtlaufzeit von L(p) = u^u*B_2 = u^u*p^(1/u) ansetzen. Um die Laufzeit zu minimieren, machen wir den Ansatz dL/du = 0, also - p^(1/u)*u^(u - 2)*(ln(p) - u^2*ln(u) - u^2) = 0 => ln(p) = u^2(1 + ln(u)) Umstellen liefert uns eine asymptotische obere Schranke für die Lösung u_(opt): u_(opt) ~ sqrt((2 ln(p))/(ln(ln(p)))), woraus wir mit B_2 ~ exp(1/2*sqrt(2 ln(p) ln(ln(p)))) die entsprechende Wahl für B_2 erhalten. Darüberhinaus ist auch die Bestimmung der asymptotischen Laufzeit möglich. Zur Übersichtlichkeit setzen wir q := ln(p) und bekommen nach Einsetzen L(p)|= exp(u*ln(u) + 1/u*q) | |= exp(sqrt((2q)/(ln(q)))*1/2*(ln(2q) - ln(ln(q))) + sqrt((ln(q))/(2q))*q) | |= exp(1/2*sqrt((2q)/(ln(q)))*ln(q)*(1 + o(1)) + 1/2*sqrt(2q*ln(q))) | |= exp(1/2*sqrt(2q*ln(q))*(1 + o(1)) + 1/2*sqrt(2q*ln(q))) | |= exp(sqrt(q*ln(q)*(2 + o(1)))) = exp(sqrt(ln(p)*ln(ln(p))*(2 + o(1)))) Die Laufzeit ist somit subexponentieller Natur. Leider gibt es zu wenige glatte Zahlen, um daraus einen effizienten Algorithmus zu erhalten. Jetzt kommt möglicherweise der Einwand, dass man die optimalen Werte für B_2 und die Kurvenanzahl nicht kennt, da ja auch p nicht bekannt ist. In der Praxis geht man von einer bestimmten Größe von p aus und macht die entsprechenden Tests. Schlagen diese fehl, so wechselt man zur nächsten Größenordnung. Gegenüber dieser ist der Aufwand der ersten Tests vernachlässigbar klein.

7. Quadratisches Sieb

Wir rufen uns noch mal die Fermatmethode ins Gedächtnis: Die gegebene Zahl N als Differenz zweier \(nichttrivialer) Quadrate dargestellt liefert uns wegen N = x^2 - y^2 = (x - y)(x + y) zwei ebenso nichttriviale Faktoren von N. Wir verallgemeinern jetzt diese Idee: Gegeben sei eine Kongruenz x^2 == y^2 (mod N), dann gilt (x - y)(x + y) == 0 (mod N) Wenn diese Kongruenz nichttrivial ist, d. h. es gilt weder x - y == 0 (mod N) noch x + y == 0 (mod N), so bekommen wir ebenfalls mit ggT(x - y,N) und ggT(x + y,N) zwei Faktoren von N geliefert. Die Idee des Quadratischen Siebes besteht darin, nicht direkt solche kongruenten Quadrate zu bestimmen, sondern sie aus betragskleinen quadratischen Resten zu kombinieren. Das lässt sich am besten durch ein Beispiel demonstrieren: Sei N = 517631, sqrt(N) = 719,4... . Das Fermatverfahren würde jetzt bei x_0 = 720 aufsteigend testen, ob die Differenz x_i^2 - N ein Quadrat ist. Wir bekommen dabei u. a. 724^2 == 5*7*11*17 (mod N) 739^2 == 2*5*7*11*37 (mod N) 741^2 == 2*5^2*17*37 (mod N) Bei Fermat würden wir noch bis 816^2 gehen, bevor wir ein echtes Quadrat erhalten. Man sieht aber sehr leicht, dass bereits die drei obigen Zahlen zusammenmultipliziert auch auf der rechten Seite ein Quadrat ergeben, nämlich (724*739*741)^2 == (2*5^2*7*11*17*37)^2 (mod N) => 473961^2 == 351126^2 (mod N) und damit ggT(473961 - 351126,N) = 431 sowie ggT(473961 + 351126,N) = 1201. Wenn man es also geschickt anstellt, kann man sich viel Arbeit ersparen. Die Idee der Kombination quadratischer Reste gab es schon vor 80 Jahren. Eines der ersten darauf basierenden Verfahren war die Kettenbruchmethode, die in den 60er Jahren recht populär war. Abgelöst wurde sie aber durch das seit 1981 entwickelte Quadratische\-Sieb\-Verfahren [4]. Dieses arbeitet in zwei Stufen: Im Siebschritt werden einerseits hinreichend viele quadratische Kongruenzen \(Relationen) erzeugt, im Auswahlschritt wird andererseits versucht, diese zu einem Quadrat x^2 == y^2 (mod N) zu kombinieren. Haben wir eine solche Kongruenz gefunden, so ist sie mit Wahrscheinlichkeit 1 - (1/2)^k nichttrivial, wenn k die Anzahl der Primteiler von N ist \- da jeder Primfaktor p von N theoretisch mit gleicher Wahrscheinlichkeit in x - y wie in x + y enthalten sein kann. Siebschritt Aus dem Beispiel ist vielleicht schon die Methode ersichtlich, mittels der wir an die begehrten Relationen gelangen können. Wir erzeugen betragskleine quadratische Reste r_i, die nur kleine Primteiler enthalten. Diese kann man mit hoher Wahrscheinlichkeit mit anderen Resten kombinieren, die dieselben Primteiler aufweisen. Kombinieren bedeutet hier zusammenmultiplizieren, so dass die jeweiligen Primteiler in gerader Potenz enthalten sind. Klar ist dabei: Je größer ein Primteiler, desto weniger Relationen werden wir finden, die diesen enthalten. Wir sind also an "glatten" quadratischen Resten interessiert. Die Primteiler, die wir zulassen, fassen wir in einer Faktorbasis zusammen. \boxon\frameon\stress\ Definition \(Faktorbasis):\normal Sei B \el\ \IN. Eine Faktorbasis zu B ist eine Menge \calF = {-1, p_2, ..., p_k } mit Primzahlen p_2 ..., p_k <= B.\boxoff\frameoff Negative Reste sind ebenso gewollt, weswegen wir p_1 := -1 mit aufnehmen. Daneben brauchen wir noch ein Siebpolynom, das die quadratischen Reste erzeugt. Dieses ist von der Form Q(i) = (i + floor(sqrt(N)))^2 - N Wir können bereits jetzt die Faktorbasis auf bestimmte Primzahlen p_i einschränken, da in von einem Siebpolynom Q(i) erzeugten Resten r_i nicht beliebige Primteiler vorkommen können. Welche das sind, bekommen wir über die Berechnung des Legendresymbols heraus. \boxon\frameon\stress\ Definition (Legendresymbol):\normal Sei a \el\ \IZ und p eine Primzahl. Unter dem Legendresymbol versteht man die Schreibweise (a/p) := cases(0, wenn p \| a; 1, wenn a quadratischer Rest modulo p ist; -1, wenn a quadratischer Nichtrest modulo p ist)\boxoff\frameoff Eine Primzahl p kann nur dann ein Teiler von Q(i) sein, falls (i + floor(sqrt(N)))^2 == N (mod p) gilt, was sofort (N/p) = 1 impliziert. Bei Erstellung der Faktorbasis wird daher zu jeder Primzahl das Legendresymbol ausgewertet. Das geht auch für große Primzahlen sehr schnell, da es einige einfache Rechenregeln für das Legendresymbol gibt. Sieht man von der 0 ab, so gibt es modulo einer ungeraden Primzahl genauso viele quadratische Reste wie Nichtreste; im Endeffekt fallen dadurch ca. die Hälfte aller Primzahlen durchs Raster. Als nächstes benötigen wir das Siebintervall. Dieses definiert diejenigen i \el\ \IZ, für die wir die Werte Q(i) verwenden. Es ist von der Form I_\epsilon = {i \el\ \IZ: -N^\epsilon <= i <= N^\epsilon } wobei 0 <= \epsilon <= 1/2 gilt. Das bewirkt, dass die damit gewonnenen quadratischen Reste von der Größenordnung Q(i) \el\ \Theta(N^(1/2 + \epsilon)) sind. Wir erzeugen uns also fortlaufend Werte Q(i) und schauen, ob diese über der Faktorbasis \calF zerfallen, d. h. Q(i) besitzt nur Primfaktoren aus der Faktorbasis. Die naive Methode, dazu eine Probedivision durch alle Faktoren p aus \calF durchzuführen, ist uns dabei viel zu langsam. Stattdessen bedienen wir uns eines deutlich schnelleren Siebverfahrens, das auf der Äquivalenz p^s \| Q(i) <=> p^s \| Q(i + l*p^s) mit l \el\ \IZ, s \el\ \IN beruht. Dabei lösen wir zunächst die Kongruenz Q(i) == 0 (mod p_j^s) für alle Primzahlen p_j \el\ \calF und in Frage kommenden Exponenten s. Man beachte, dass Q ein quadratisches Polynom ist. Modulo einer Primzahl haben solche Polynome höchstens zwei Nullstellen \(wir müssen demzufolge auch alle Lösungen betrachten). Die Nullstellen lassen sich auch für große Primzahlen schnell bestimmen; das gilt ebenfalls für die Nullstellen modulo einer Primzahlpotenz. Haben wir nun zwei Lösungen i_1 und i_2 erhalten, so bekommen wir alle weiteren einfach durch Addition ganzzahliger Vielfache l*p_j^s zu i_1 bzw. i_2. Die Ergebnisse werden in einer Siebtabelle festgehalten. Die Zeilen markieren den Index i und die Spalten die Primzahlen p_j der Faktorbasis. Die Einträge sind die Vielfachheiten s des Vorkommens der p_j in der Faktorzerlegung von Q(i). Untenstehend zu sehen ist die Siebtabelle für unser Eingangsbeispiel N = 517631 und das Siebintervall I = intervall(-24, 24).
Bild
In die "finale" Siebtabelle kommen natürlich nur die Q(i), die über der Faktorbasis \calF zerfallen. Um festzustellen, ob das der Fall ist, müssen wir während des Siebvorgangs Q(i) durch gefundene Faktoren p_j^s dividieren. Wird dadurch am Ende Q(i) zu 1 reduziert, so ist Q(i) über \calF vollständig zerlegbar. Auswahlschritt Nachdem wir im ersten Teil des Verfahrens hinreichend viele \- was "hinreichend" bedeutet, werden wir gleich sehen \- Relationen der Form x_i^2 == Q(i) (mod N) gefunden haben, werden diese nun im zweiten Teil zur gesuchten Lösung kombiniert. Wir haben also insgesamt l quadratische Reste Q(i_1), ..., Q(i_l) gegeben und suchen jetzt eine Auswahl { i_m_1, ..., i_m_n } \subsetequal\ { i_1, ..., i_l }, sodass im Produkt Q(i_m_1)*...*Q(i_m_n) == (x_i_m_1*...*x_i_m_n)^2 (mod N) auch auf der linken Seite ein echtes Quadrat steht. Dazu müssen die Elemente p_j der Faktorbasis in der Faktorzerlegung der linken Seite in einer geraden Potenz vorkommen. Sind s_ij die zugehörigen Exponenten, so muss also die Gleichung z_1 s_1j + z_2 s_2j + ... + z_l s_lj == 0 (mod 2) mit Koeffizienten z_1, ..., z_l \el\ {0, 1} gelten. Diese Eigenschaft gilt natürlich für alle k Elemente von \calF, sodass wir ein Gleichungssystem Az == 0 (mod 2) der Form (s_11, \cdots, s_l1; \vdots, \ddots, \vdots; s_1k, \cdots, s_lk)*(z_1; \vdots; z_l) == 0 (mod 2) bekommen. Im Lösungsvektor z sind genau die n Bit gesetzt, die diejenigen Relationen auswählen, welche sich zur gesuchten Lösung kombinieren lassen. Zu lösen ist also ein lineares Gleichungssystem über \IF_2, wobei im Fall l > k sogar eine Lösung garantiert ist. Falls sich als Lösung eine triviale Kongruenz ergibt, muss wenigstens eine weitere Kongruenz gefunden werden. Beispiel Bleiben wir bei unserem Beispiel N = 517631. Die Siebtabelle haben wir schon gesehen, im zugehörigen Gleichungssystem Az == 0 (mod 2) ist dann A = (1,1,1,1,0,0,0,0,0;1,0,1,1,1,0,0,1,1;0,1,0,0,1,1,1,1,0;0,1,0,1,0,1,0,1,0;1,0,0,1,0,1,0,1,0;1,0,1,0,1,0,0,0,0;0,1,0,0,1,1,0,0,1;0,0,1,1,0,0,0,0,0;0,1,0,0,0,0,0,1,1) und z = (0;0;0;0;0;1;0;1;1) Um zwei kongruente Quadrate zu erzeugen, müssen also die Relationen 6, 8 und 9 kombiniert werden \(entspricht den Werten i = 5, 20 und 22). Erweiterungen / Verbesserungen Der Siebschritt ist natürlich parallelisierbar, da man unabhängig voneinander verschiedene Werte Q(i) berechnen und über verschiedenen p \el\ \calF sieben kann. Man kann aber noch weitere interessante Erweiterungen einbauen. 1) Verwendung von partiellen Relationen Man kann die Forderung, dass ein quadratischer Rest über \calF zerlegbar sein muss, etwas abschwächen. Man lässt in der Faktorzerlegung einen Primfaktor q außerhalb von \calF zu, der aber eine bestimmte \(nicht zu hohe) Schranke nicht überschreiten darf. Findet man zwei solche sogenannten partiellen Relationen mit demselben Faktor q, so lässt sich q durch Kombination beider Relationen eliminieren. Damit man eine Chance auf solche Paare hat, darf q aber nicht zu groß geraten. 2) Verwendung von Heuristiken Weiterhin hat man herausgefunden, dass sich das Sieben nach großen Primpotenzen p^s nur für kleine p lohnt und schränkt sich hier entsprechend ein \- auch wenn dadurch möglicherweise Relationen übersehen werden. Eine weitere brauchbare Modifikation ist das logarithmische Sieben. Statt die Werte Q(i) durch gefundene Faktoren p^s zu dividieren, hält man sich eine Tabelle mit den Logarithmen der p^s bzw. der Q(i). Eine Division ersetzt man dann durch eine Subtraktion des entsprechenden Logarithmus. Dahinter steckt die Tatsache, dass eine Subtraktion schneller ausgeführt wird als eine Division. Die Logarithmen werden mit einer hinreichend großen Genauigkeit gespeichert. Ein Rest zerfällt über \calF, falls die Subtraktionen einen Wert sehr dicht bei 0 ergeben. Nachteil: die Rundungsfehler stellen eine \(theoretische) Fehlerquelle dar. 3) Verwendung von Mehrfachpolynomen Wir benutzten bis jetzt ein einziges Siebpolynom der Gestalt Q(x) = x^2 - N. Nur für wenige x sind die so erzeugten Reste wirklich klein; und man ist natürlich an möglichst kleinen Resten interessiert, da diese mit höherer Wahrscheinlichkeit über der Faktorbasis zerfallen. Daher gibt es eine erweiterte Variante, die variable Polynome der Form Q(x) = (ax + b)^2 - N verwendet. Wählt man hier a und b so, dass a ein Teiler von b^2 - N ist, so gilt Q(x) = (ax + b)^2 - N = a^2 x^2 + 2abx + b^2 - N = a*(ax^2 + 2bx + c) für eine ganze Zahl c. Das bedeutet: Q(x) ist immer durch a teilbar, sodass man nur die Werte Q(x)\/a betrachten muss. Man kann sich also ein a wählen und erhält dadurch mehrere Siebpolynome. Ein zu großes a führt aber leider dazu, dass die Werte Q(x) schneller anwachsen. Um ein zugehöriges b zu bekommen, löst man die Kongruenz b^2 == N (mod a). Auch hier kann man tricksen, da die Zahl der Lösungen dieser Kongruenz umso größer ist, je mehr Primfaktoren a besitzt. Man wählt daher gerne solche a mit vielen verschiedenen kleinen Primfaktoren und erhält entsprechend viele Siebpolynome. 4) Eine Weiterentwicklung: Das Zahlkörpersieb Ende der 80er Jahre gelang eine deutliche Verbesserung durch Erfindung des Zahlkörpersiebes. Das Verfahren benutzt algebraische Zahlkörper und erzeugt viel glattere Relationen als das originale QS. Wer sich für dieses Verfahren interessiert, lese z. B. in [5] weiter. Laufzeit Wählen wir die Faktorbasis sehr groß, so finden wir auch schnell geeignete Relationen, benötigen aber auch viele davon und müssen anschließend noch ein Riesengleichungssystem lösen. Ist die Faktorbasis dagegen klein, suchen wir mitunter sehr lange. Gesucht ist also wieder mal der goldene Mittelweg. Fangen wir mit dem Siebverfahren an. \calF enthält alle Primzahlen <= B. Hat man mit dem Siebpolynom n quadratische Reste gewonnen, so werden zu jeder Primzahl p \el\ \calF insgesamt n\/p Eintragungen in der Siebtabelle vorgenommen. Für den Gesamtaufwand ergibt sich daraus sum(n/p, p \el\ \calF) \approx n*int(1/(k*ln(k)), k, 2, B) \approx n*ln(ln(B)) Die Integralabschätzung bekommt man aus dem Primzahlsatz, aus dem man die Größenordnung k*ln(k) für die k\-te Primzahl folgern kann. Pro berechnetem quadratischen Rest brauchen wir also gerade einmal ln(ln(B)) Operationen für das Sieben. Jetzt müssen wir uns natürlich überlegen, wie viele quadratische Reste wir durchprobieren müssen, bis uns eine der gewünschten Relationen über den Weg läuft. Für diese muss der Rest über \calF zerlegbar, also B\-glatt sein. Dazu benötigen wir wieder die in Kapitel 6 vorgestellte Glattheitsfunktion \psi und den Satz von Canfield, Erdös und Pomerance. Nehmen wir an, alle vom Siebpolynom erzeugten Reste sind im Betrag durch x beschränkt. Es ist dann x*\psi(x,B)^(-1) die zu erwartende Anzahl an benötigten Versuchen, um einen B\-glatten Rest zu bekommen. Um im Auswahlschritt das Gleichungssystem lösen zu können, benötigen wir etwa \pi(B) Relationen. Wir können also eine Gesamtlaufzeit von L(x) = ln(ln(B))*\pi(B)*x*\psi(x,B)^(-1) ansetzen. Der Primzahlsatz sagt uns \pi(B) \approx B/ln(B), wir können ln(ln(B))*\pi(B) also mit B großzügig nach oben abschätzen. Um den Satz von Canfield, Erdös und Pomerance anzuwenden, setzen wir B := x^(1/u), also L(x) = x^(1/u)*x*\psi(x,x^(1/u))^(-1) Anwenden des Satzes: L(x) = x^(1/u)*u^u Um die Laufzeit zu minimieren, machen wir wieder den Ansatz dL/du = 0, was uns auf ln(x) = u^2(ln(u) + 1) führt. Man beachte die Ähnlichkeit zur Laufzeitanalyse in Kapitel 6. Analog zu dieser bekommen wir u_(opt) ~ sqrt((2 ln(x))/(ln(ln(x)))) Fehlt nur noch das Einsetzen und Vereinfachen: L(x)|= exp(1/u*ln(x) + u*ln(u)) | |= exp(ln(x)*sqrt((ln(ln(x)))/(2*ln(x))) + 1/2*ln((2*ln(x))/(ln(ln(x))))*sqrt((2*ln(x))/(ln(ln(x))))) | |= exp(sqrt(1/2*ln(x)*ln(ln(x))) + 1/2*ln(ln(x))*sqrt((2*ln(x))/(ln(ln(x))))) | |= exp(sqrt(2*ln(x)*ln(ln(x)))) Wie schon erwähnt sind die quadratischen Reste im Betrag durch N^(1/2 + \epsilon) beschränkt, wobei man mit \epsilon -> 0 (für N -> \infty) auskommt. Also: L(N)|= exp(sqrt(2*ln(N^(1/2 + o(1)))*ln(ln(N^(1/2 + o(1))))) | |= exp(sqrt((1 + o(1))*ln(N)*ln(ln(N)))) Man kann jetzt noch nachrechnen, dass die optimale Wahl von B in der Größenordnung B \approx exp((1/2 + o(1))*sqrt(ln(N)*ln(ln(N)))) liegt. Soweit der Siebschritt. Das ganze würde natürlich gar keinen Sinn machen, wenn die eigentliche Komplexität im Auswahlschritt läge. Dort haben wir ein Gleichungssystem mit einer l \cross\ l \- Matrix (wobei l \approx B) zu lösen. Die Gauß\-Elimination hat zwar allgemein eine Laufzeit von \Theta(l^3), doch handelt es sich hier um extrem dünn besetzte Matrizen. Man kann ja leicht nachrechnen, dass die Anzahl der auf 1 gesetzten Stellen in einer Spalte durch etwa ln(N) beschränkt ist. In der Praxis ergibt sich daher eine Laufzeit von B^(2 + o(1)) für den Auswahlschritt, wobei man eher speziell auf solche Matrizen zugeschnittene Algorithmen verwendet, z. B. das "Block Lanczos"\-Verfahren. Der Auswahlschritt ist gegenüber dem Siebschritt fast vernachlässigbar. Das ist auch gut, da sich ersterer \- im Gegensatz zu letzterem \- schlecht parallelisieren lässt. Die Laufzeit hat starke Ähnlichkeit zur Laufzeit der Elliptische\-Kurven\-Methode. Das ist aber kein Zufall, da die Komplexität beider Verfahren durch glatte Zahlen bestimmt wird. Das QS unterscheidet sich von ECM dadurch, dass der Aufwand ausschließlich von der Länge der Eingabe N abhängt und unabhängig von der Größe der Primteiler von N ist. In der Praxis läuft es meist auf eine Arbeitsteilung hinaus. Faktoren bis etwa \wurzel(3,N) werden mit ECM schneller gefunden. Bleiben dagegen genau zwei Faktoren größer als \wurzel(3,N) übrig, so gibt man dem QS den Vorzug, welches in diesem Fall seine Stärken ausspielen kann.

8. Ein Faktorisierungs-Programm in C

Manchem ist sicher das Unix-Kommando "factor" ein Begriff, das bei Eingabe einer natürlichen Zahl eine Liste der Primfaktoren ausgibt. Leider hat dieses Programm einige Beschränkungen. Zum Beispiel darf die Eingabe die Größe von 64 Bit nicht überschreiten; bei größeren Zahlen wird noch nicht einmal ein einfacher Primtest gemacht. Daher möchte ich ein kleines Programm vorstellen, das mit diesen Unzulänglichkeiten (endlich!) aufräumt. Man kann es unter folgendem Link herunterladen: factor.zip Es verwendet die Verfahren Probedivision, Pollard-Rho und ECM, wobei für die Eingabe (theoretisch) keine Beschränkung existiert. Faktoren dürften hier auch deutlich schneller gefunden werden als mit dem gleichnamigen Unixbefehl. Die Verwendung erfolgt aus dem Programmverzeichnis heraus mit ./factor [Zahl] unter Linux bzw. factor [Zahl] unter Windows. Das Programm liegt auch als C-Quelltext vor, über Hinweise und/oder Verbesserungsvorschläge freue ich mich daher besonders. Wer stattdessen einmal das QS-Verfahren ausprobieren möchte, kann ja die interessante LISP-Implementierung testen, die in diesem Thread vorgestellt wurde.

Zitierte Artikel

[1] R. S. Lehman: "Factoring Large Integers", Mathematics of Computation 28, 1974, S. 637-646 [2] P. L. Montgomery: "Speeding the Pollard and Elliptic Curve Methods of Factorization", Mathematics of Computation 48, 1987, S. 243-264 [3] P. L. Montgomery: "An FFT Extension of the Elliptic Curve Method of Factorization", Dissertation, University of California, 1992 [4] C. Pomerance: "The Quadratic Sieve Factoring Algorithm", Lecture Notes in Computer Science 209, 1985, S. 169-182 [5] A. K. Lenstra, H. W. Lenstra, Jr.: "The Development of the Number Field Sieve", Lecture Notes in Mathematics 1554, 1993

 
Dieser Artikel ist enthalten in unserem Buch
Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Informatik :: Kryptographie :: Elliptische Kurven :: Primfaktorzerlegung :: Primzahlen :: Zahlentheorie :
Faktorisierung großer Zahlen [von Kay_S]  
Ein Artikel über Faktorisierungsverfahren. Es werden der Reihe nach die meisten wichtigen Verfahren vorgestellt und analysiert: Probedivision, Fermat-Faktorisierung, Lehman-Algorithmus, Pollard-Rho-Verfahren, (p-1)-Verfahren, Elliptische-Kurven-Methode, Quadratisches Sieb.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 18501
 
Aufrufstatistik des Artikels
Insgesamt 2876 externe Seitenaufrufe zwischen 2012.01 und 2021.12 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com10%0 %
https://google.com602.1%2.1 %
https://duckduckgo.com240.8%0.8 %
https://matheplanet.com20.1%0.1 %
https://www.bing.com140.5%0.5 %
https://google.ch10%0 %
https://www.ecosia.org80.3%0.3 %
http://google.de179562.4%62.4 %
https://google.de2498.7%8.7 %
http://google.ru2177.5%7.5 %
http://google.fr1776.2%6.2 %
http://google.rs953.3%3.3 %
http://google.is341.2%1.2 %
http://google.pl341.2%1.2 %
https://google.ru240.8%0.8 %
http://images.google.de210.7%0.7 %
http://google.it190.7%0.7 %
http://google.com80.3%0.3 %
http://www.bing.com341.2%1.2 %
http://www.bookmerken.de70.2%0.2 %
http://avira.search.ask.com80.3%0.3 %
http://de.search.yahoo.com90.3%0.3 %
http://m.c-plusplus.net20.1%0.1 %
https://startpage.com20.1%0.1 %
http://10.0.0.1:191020.1%0.1 %
https://www.startpage.com20.1%0.1 %
http://search.conduit.com10%0 %
http://search.tb.ask.com20.1%0.1 %
https://metager.de10%0 %
http://10.101.1.2:191010%0 %
http://ecosia.org20.1%0.1 %
http://de.images.search.yahoo.com10%0 %
http://cc.bingj.com10%0 %
http://suche.t-online.de60.2%0.2 %
http://www.cs.hs-rm.de10%0 %
http://de.yhs4.search.yahoo.com20.1%0.1 %
http://alicesuche.aol.de10%0 %
https://cse.google.com10%0 %
http://search.snap.do10%0 %
http://10.69.0.1:191010%0 %
http://de.ask.com10%0 %
http://suche.aol.de10%0 %
http://suche.web.de20.1%0.1 %
http://suche.aolsvc.de10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 9 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.12.02 21:38fav.php?agid=1&keyword=Primzahlen
2021.11.08-2021.11.30 (8x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 2778 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (572x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (164x)https://google.de/
201201-01 (144x)http://google.ru/imgres?q=cotangens tabelle
201206-06 (132x)http://google.fr/imgres?q=rho pollard
201210-12 (113x)http://google.de/url?sa=t&rct=j&q=quadratisches zahlensieb
201311-11 (106x)http://google.de/url?sa=t&rct=j&q=faktorisierung x^2-y^2 fermat
201202-02 (95x)http://google.rs/url?sa=t&rct=j&q=mp faktorisierung großer zahlen
201205-05 (87x)http://google.de/url?sa=t&rct=j&q=wurzel faktorisieren
201211-11 (83x)http://google.de/url?sa=t&rct=j&q=primfaktorzerlegung pollard-rho-algorithmus
201204-04 (83x)http://google.de/url?sa=t&rct=j&q=teilbarkeit große zahlen
201209-09 (80x)http://google.de/url?sa=t&rct=j&q=quadratische zahlensieb
201207-07 (78x)http://google.de/url?sa=t&rct=j&q=siebpolynom
201301-01 (74x)http://google.de/url?sa=t&rct=j&q=quadratisches sieb software
201401-01 (67x)http://google.de/url?sa=t&rct=j&q=faktorisierung natürlicher zahlen
202005-12 (56x)https://google.de/url?sa=t
201405-05 (56x)http://google.de/url?sa=t&rct=j&q=faktorisieren teiler wurzel
201309-09 (56x)http://google.de/url?sa=t&rct=j&q=definition faktorisieren mathe
201203-03 (54x)http://google.de/url?sa=t&rct=j&q=zahlensieb dauer faktorisierung
201208-08 (54x)http://google.de/url?sa=t&rct=j&q=faktorisierung laufzeit
201304-04 (53x)http://google.de/url?sa=t&rct=j&q=primteiler kleiner als dritte wurzel n
2020-2021 (52x)https://google.com/
201306-06 (45x)http://google.fr/imgres?sa=X&biw=1438&bih=734&tbm=isch&tbnid=D7eUk7043V36QM:
201302-02 (43x)http://google.ru/url?sa=i&rct=j&q=
201305-05 (40x)http://google.de/url?sa=t&rct=j&q=problem der faktorisierung großer zahlen
201411-11 (36x)http://google.de/url?sa=t&source=web&cd=1&ved=0CB0QFjAA
201412-12 (34x)http://google.is/url?sa=t&rct=j&q=
201303-03 (34x)http://google.pl/imgres?start=142&um=1&sa=N&biw=1366&bih=643&authuser=0&tbm=i...
201307-07 (33x)http://google.de/url?sa=t&rct=j&q=pollard roh keine lineare funktionen
201505-05 (30x)http://google.ru/url?sa=t&rct=j&q=
201308-08 (25x)http://google.de/url?sa=t&rct=j&q=fermat zahl 7 pollard rho
202102-02 (24x)https://google.ru/
202103-03 (23x)https://google.de/search?biw=853
2016-2017 (20x)http://images.google.de/url?sa=t&rct=j&q=
201404-04 (19x)http://google.it/search?ei=itA-U-rUAcLoswb21YCgAw&q=rho zahl
201504-04 (19x)http://google.de/url?sa=t&source=web&cd=6&ved=0CC4QFjAF
2020-2021 (18x)https://duckduckgo.com/
201409-09 (10x)http://google.de/url?sa=t&rct=j&q=vorperiode und periode einer zufallsfolge
2017-2018 (8x)http://google.com/search
201304-04 (8x)http://www.bing.com/search?q=nullstellen elliptische funktion primzahl&qs=n&f...
2020-2021 (7x)https://www.bing.com/
201501-01 (7x)http://www.bookmerken.de/
2020-2021 (7x)https://www.ecosia.org/
201307-07 (6x)http://avira.search.ask.com/web?apn_dtid=^YYYYYY^YY^DE&apn_dbr=ff_22.0&itbv=1...
202108-08 (6x)https://google.de
201604-04 (5x)http://google.de/url?sa=t&source=web&cd=10&rct=j&q=faktorisierungs programm
2020-2021 (4x)https://duckduckgo.com
201512-12 (4x)http://google.de/url?sa=t&rct=j&q=faktorisierung sehr großer zahlen
2013-2015 (4x)http://www.bing.com/search?q=matroids mathe faktorisierung&qs=n&form=QBRE&pq=...

[Top of page]

"Mathematik: Faktorisierung großer Zahlen" | 11 Comments
The authors of the comments are responsible for the content.

Re: Faktorisierung großer Zahlen
von: Gockel am: Sa. 15. März 2008 20:17:11
\(\begingroup\)Hallo Kay. Ein toller Artikel ist dir da gelungen. Inhaltlich sehr interessant, optisch sehr ansprechend, niemals langweilig. Kurzum: Klasse! mfg Gockel.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: spitzwegerich am: Mo. 17. März 2008 01:24:34
\(\begingroup\)Ein schöner Artikel. An wichtigen Faktorisierungsmethoden wäre noch das allgemeine Zahlkörpersieb zu nennen.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Gockel am: Mo. 17. März 2008 16:20:24
\(\begingroup\)Das wurde doch genannt!? \quoteon 4) Eine Weiterentwicklung: Das Zahlkörpersieb Ende der 80er Jahre gelang eine deutliche Verbesserung durch Erfindung des Zahlkörpersiebes. Das Verfahren benutzt algebraische Zahlkörper und erzeugt viel glattere Relationen als das originale QS. Wer sich für dieses Verfahren interessiert, lese z. B. in [5] weiter. \quoteoff mfg Gockel.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: spitzwegerich am: Fr. 21. März 2008 00:30:48
\(\begingroup\)Stimmt, da stehts ja. Hab ich wohl überlesen, sorry.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Ex_Mitglied_40174 am: So. 23. März 2008 17:16:07
\(\begingroup\) \ \Theta(sum(\wurzel(6, N)/(4 \sqrt(k)), k=1, wurzel(3, N))) = \Theta(int(\wurzel(6, N)/(4 \sqrt(k)), k, 1, wurzel(3, N))) = \Theta(wurzel(3, N)) Unter welchen Voraussetzungen an die Funktion unter der Summe/Integral kann man so argumentieren?\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Gockel am: So. 23. März 2008 18:30:33
\(\begingroup\)Es funktioniert z.B. für alle monoton fallenden, positiven Funktionen. mfg Gockel.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Ex_Mitglied_40174 am: So. 23. März 2008 18:51:51
\(\begingroup\)Hm... auch mit Theta? Ich glaube zu sehen, dass das Integral dann höchstens so schnell wächst wie die Summe... aber andersrum? Hast du vielleicht irgendein Literaturtip für solche Sachen, evtl noch allgemeiner? Ich nehm natürlich auch gern nen Beweis :) \(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Kay_S am: So. 23. März 2008 18:59:23
\(\begingroup\) Es genügt z. B. \- stetig, monoton fallend, nach unten beschränkt Wenn f(k) diese Eigenschaften auf intervall(1, \infty) besitzt, gilt S_1 := sum(f(k),k=2,m) <= int(f(k),k,1,m) <= sum(f(k),k=1,m-1) =: S_2 S_1 ist eine Unter\-, S_2 eine Obersumme des Integrals. Und wegen der Beschränktheit von f(m) ist auch S_2 - S_1 = f(1) - f(m) beschränkt, d. h. Integral und Summe unterscheiden sich um nicht mehr als eine Konstante. Kay \(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: slurpslerp am: So. 23. März 2008 19:45:31
\(\begingroup\)Danke. Ich hatte das noch nie gesehen so... wie gesagt, wenn jemand gute Bücher weiss wo solche Sachen drinstehen... her damit :)\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Ex_Mitglied_40174 am: Mi. 16. April 2008 03:49:06
\(\begingroup\)Das vorgestellte Programm in factor.zip läuft bei mir unter Windows leider nicht. Ich habe mir den c-code mal angeschaut, die Fehlerabfragen, wenn ich zB eine 0 oder Kommazahlen eingebe funktioniert, wenn ich jedoch 11 oder 1111 eingebe, dann bricht die Berechnung mit einem kleinen Windows Fehler ab. Ist das bei euch auch so? Oder stimmt bei meinen Windows Einstellungen etwas nicht? \(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Diophant am: Do. 04. Februar 2021 12:55:11
\(\begingroup\)Diesen sehr gelungenen Artikel kannte ich bisher noch gar nicht und werde ihn in nächster Zeit einmal gründlich durcharbeiten. Nur zum vorherigen Kommentar (auch wenn er schon 13 Jahre alt ist 😉 ): unter Windows 10 läuft das Programm nach wie vor in der normalen Windows-Konsole problemlos. In der Windows Powershell muss man wie unter Linux "./factor [Zahl]" eingeben, dann funktioniert es ebenfalls. Gruß, Diophant\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]