Diskussion:Quadratisches Sieb/Archiv

Neues Siebkriterium

Es ist zunächst naheliegend nur glatte Relationen auszuwählen. Dieses Kriterium hat jedoch einen großen Nachteil. Eine effiziente Prüfung ist nicht möglich. Es kann nur dann erkannt werden, ob eine Zahl glatt ist, wenn ihre kleinen Primteiler bestimmt werden und zusätzlich bestimmt wird welche Potenzen dieser Primfaktoren auftreten. Mit anderen Worten, eine unvollständige Faktorisierung in die kleinen Pimzahlen und der Potenzen ist erforderlich.

Bei der Idee von Pommerance wird ausgenutzt, dass sobald eine Primzahl p in den Zerlegungen der Q(k) für ein k auftritt, p erneut als Teiler auftritt, wenn man ein Vielfaches der Primzahl zu k addiert. Diese Überlegung gilt in gleicher Weise auch für das Quadrat $p^{2}$, so können durch Addition Viefacher von $p^{2}$ leicht weitere Q(k) mit dieser Quadratzahl als Faktor gefunden werden. Suchen wir nach denjenigen Q(k) mit $p^{2}$ als Faktor, kommen nur solche in Frage die bereits p als Faktor enthalten. Taucht z.B. der Faktor 3 auf, gibt es in einem Interval der Länge 3 noch ein weiteres Q(k) mit mit diesem Faktor. Die 9 kann nur auftreten, wenn in den beiden Sequenzen mit dem Faktor 3 auch die 9 auftritt. Offensichtlich sind die Q(k) mit Quadratzahlen als Faktoren besonders günstig. Es erscheint daher sinnvoll nur derartige Q(k) auszusieben, die Quadrate von Primzahlen enthalten.

Der Vorteil dieses neuen Siebkriteriums ist, dass tatsächlich sehr effizient diejenigen Relationen ausgesiebt werden können, die keine Quadrate (kleiner) Primzahlen als Teiler enthalten. Die meisten glatten Zahlen enthalten jedoch Quadrate und eventuell sogar höhere Potenzen der kleinen Primzahlen. Durch diese etwas verschärfte Siebbedingung werden folglich nur mit minmaler Wahrscheinlichkeit glatte Relationen verworfen. Auf der anderen Seite wird die Prüfung aber erheblich beschleunigt, so dass insgesamt das Verfahren beschleunigt wird.

Die ggT-Methode

Das Aussieben der nicht glatten Relationen kann gegenüber der Idee von Pommerance noch mit einem anderen Verfahren stark beschleunigt werden. Die Bedingung, dass Q(k) glatt ist bzw. als Produkt der Fakoren $p_{1},p_{2},...,p_{n}$ geschrieben werden kann lässt sich in der Form

$ggT(p_{1}\cdot p_{2}\cdot p_{3}\cdots p_{n},Q(k))=Q(k)$

schreiben, falls die jeweils die größten auftretenden Potenzen der einzelnen Primzahlen in die Fakorbasis aufgenommen werden. Im Falle einer kleineren Faktorbasis lässt sich der ggT ohne weiteres berechnen. Bei über tausend Faktoren wird es schwierig diese alle zu multiplizieren. In diesem Fall können aber z.B. jeweils einige 100 Faktoren multipliziert werden. Dann ist entsprechend das Produkt der ggT-Werte zu bilden.

Pollard-Rho-Methode oder Rekursion

Wesentlich effizienter als die Probedivision, auch als die entsprechend der Idee von Pommerance beschleunigte Varaiante, ist beispielsweise die Pollard-Rho-Methode. Die Zahl der Iterationen zur Bestimmung eines Faktors p bei diesem Verfahren proportional ${\sqrt {p}}$. Falls n aus zwei etwa gleich großen Faktoren besteht, ist die asymtotische Laufzeit O(n^1/4). Die Faktorisierung einer 100-stelligen Zahl ist allerdings direkt kaum möglich. Zur Faktorisierung der glatten Relationen ist die Methode jedoch hervorragend geeignet, da die glatten Zahlen in viele Fakoren zerfallen. Zerfällt die Zahl in m etwa gleich große Faktoren ist die Zahl der Iterationen zur vollständigen Faktorisierung O(n^1/2m*log(m)). Die Laufzeit auf einem PC zur Faktorisierung einer S-glatten Zahl mit $S=10^{6}$ liegt im Bereich von Sekunden. Die Pollard-Rho-Methode hat noch weitere Vorteile. Sie extrem einfach zu implementieren und benötigt kaum Speicherplatz.

Bei extrem großen Zahlen mit über 300-Stellen ist die rekursive Anwendung des Verfahrens die beste Lösung. Ein verbleibender Faktor in der Größenordnung von 10¹² in den Relationen könnte selbst mit einem Verfahren ähnlich dem Quadrischen Sieb faktorisiert werden. Auf einem größeren Rechner liegen die Laufzeiten immer noch im Sekundenbereich.

Weitere Relationen Q(kn)

Es bietet sich an statt der Relationen $Q(x)=x^{2}-n$ weitere der Form $Q(x)=x^{2}-k\cdot n$ mit einer kleinen Zahl k zu betrachten. Dies entspricht der Faktorisierung kleiner Vielfacher von n. Über den ggT mit n können weiterhin in 50 % der Fälle die Faktoren p und q bestimmt werden. Dieses Vorgehen hat den Vorteil, dass kleinere Zahlen auftreten, falls für jedes k nur ein Bruchteil der Relationen berechnet werden. In den Relationen treten dann auch die Primzahlen auf, die für k=1 nicht auftreten.

Bei Verwendung der Pollard-Rho-Methode erschwert dies die Faktorisierung der Relationen in keiner Weise. Dies bedeutet, dass sich bei fester Schranke S etwa doppelt so viele Primfaktoren ergeben bzw. die Schranke etwa halbiert werden kann und trotzdem gleich viele Faktoren auftreten.

Es nur erforderlich zu einer festen Basis mit N Faktoren N+1 Relationen zu finden, die sich vollständig faktorisieren lassen. Bei kleinem S können viele Realtionen nicht vollständig faktorisiert werden. Dafür müssen jedoch auch entsprechend weniger glatte Relationen gefunden werden und der Aufwand zur Faktorisierung nimmt erheblich ab.

Schließlich kann die -1 als Faktor aufgenommen werden. Dadurch können symmetrische Intervalle um ${\sqrt {k\cdot n}}$ gebildet werden. Damit können erneute kleinere Zahlenwerte betrachtet werden, wodurch die Chance steigt glatte Realationen zu finden und der Aufwand zur Faktorisierung der Realtionen abnimmt. Tatsächlich genügt es jeweils nur x=$\lceil {\sqrt {k\cdot n}}\rceil$ und $\lfloor {\sqrt {k\cdot n}}\rfloor$für einen Wert k zu betrachten.

Potential des Verfahrens

Trotzdem scheint das in der "Fabel" beschriebene Verfahren von Kraichik im Prinzip tatsächlich geeignet 100-stellige oder noch größere Zahlen zu faktorisieren. Es gibt sicher viele mehr oder minder nahe liegende Ideen, um das Verfahren noch erheblich zu beschleunigen. Einige davon hatte ich in einer revertierten Fassung dieses Artikels auch benannt. Fakt ist zumindest, dass heute bereits eine 200-stellige Zahl faktorisiert wurde. Sofern man den Angaben glauben kann, war der Rechaufwand dazu im Vergleich zur Rechenleistung von modernen Hochleistungsrechnern eher gering. Ferner sind heute kaum noch aktuelle Quellen zu finden, die RSA mit einer bestimmten Schlüssellänge als wirklich längerfristig sicher einstufen. Sogar von der Firma RSA Security, die das RSA-Verfahren patentiert hatte, findet man keine derartigen Aussagen mehr. (nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) 12:22, 6. Apr 2006)

U wie Unsinn

In diesen Artikel geht um das Quadratische Sieb. Dieses findet Zahlen, deren Quadrate glatt mit einem speziellem Siebverfahren (Name!), nicht die kleinen Primzahlen!. Und nur bei diesen Zahlen wird versucht, sie in Primfaktoren zu zerlegen, alles andere ist viel zu langsam. Die Wahrscheinlichkeit, dass eine 100-stellige Zahl in Primfaktoren zerfällt, die höchstens 10 Stellen haben liegt bei 10^-10. Also ist nur eine von 10 Milliarden Zahlen in diesem Bereich glatt. Hier findest Du eine Herleitung dieser Zahlen: http://www.math.leidenuniv.nl/~reinier/ant/sieving.pdf. Dieser Beitrag ist von Carl Pomerance, dem Verfasser der "Tale of two sieves", dem Erfinder dieses Verfahrens.

Die Behauptung, dass die Häufigkeit der glatten Zahlen etwa $u^{-u}$ sei, falls man die Schranke $S=n^{1/u}$ wählt, habe ich nun schon häufiger gelesen. Eine nachvollziehbare Begründung dafür habe ich nicht finden können. Für kleinere Zahlen kann man die Häufigkeit der glatten Zahlen leicht berechnen. Hier ist die Formel jedenfalls grob falsch. Für S=5 und u=3 entsprechend n=125, sollte man nach dieser Formel etwa 5 glatte Zahlen kleiner als 125 erwarten. Es gibt jedoch weit mehr glatte Zahlen als nur 1,2,3,4 und 5. Weshalb die merkwürdige Abschätzung für größere Zahlen stimmen sollte, ist mir nicht erklärbar.

Häufigkeit glatter Zahlen

Der entscheidende Punkt zur Abschätzung der Komplexität ist die Frage nach der Häufigkeit der glatten Zahlen. Hier gibt es keine glaubhaften Abschätzungen.

Wir stellen uns vor, wir verwenden da Verfahren von Fermat, um eine große Zahl zu faktorisieren. Dieses Verfahren findet diejenige Zerlegung in zwei Faktoren mit der geringsten Differenz der Faktoren. Das Verfahren wenden wir anschließend auf die gefundenen Faktoren an. Dies setzen wir solange fort, bis alle Faktoren kleiner der Schranke S sind oder ein größerer Primfakor auftritt. Falls die Zahl in annähernd gleich große Bruchstücke zerfällt erhalten wird nach 5 Schritten, 32 Faktoren. Es sind dazu

$1+2+4+8+16=2^{5}-1$

Faktorisierungen in zwei Faktoren erforderlich. Die Zahl der Stellen, d.h. der Logarithmus der 32 Faktoren, ist etwa ein 1/32 vom Logarithmus der Zahl n = Q(k), die wir faktorisieren. Die Faktorisierung der glatten Relation ist nur möglich, falls die $2^{5}-1$ Fakoren zusammengesetzte Zahlen sind. Die Wahrscheinlichkeit bezeichnen wir mit p. Wir nehmen zur Vereinfachung an, dass die Wahrscheinlichkeit p konstant sei. Tatsächlich nimmt diese Wahrscheinlichkeit mit der Größe der Zahl zu, was das Auffinden glatter Zahlen weiter begünstigt. Die Wahrscheinlichkeit, dass alle Faktoren teilbar sind beträgt in unserer Näherung $P=p^{31}\approx {p^{\frac {ln(n)}{ln(S)}}}$.

Die Faktorisierung der Zahl n=Q(k) mit dem Fermatverfahren ist dabei nur als eine Art Gedankenexperiment zu sehen. Tatsächlich wird die verbesserte Probedivision nach der Idee von Pommerance, die Pollard-Rho-Methode oder das QS rekursiv eingesetzt.

Das Ergebnis des Gedankenexperiments legt es nahe die Schranke log(S) etwa proportional dem Logarithmus von N zu wählen, um eine konstante Wahrscheinlichkeit für glatte Zahlen zu erhalten. Mit dieser Wahl von S nimmt die Laufzeit jedoch exponentiell zu.

Für eine optimale Wahl von S muss berücksichtigt werden, dass die Wahrscheinlichkeit p nach dem Primzahlsatz von S abhängt. Die Wahrscheinlichkeit in einem Teilungsschritt beträgt mindestens $p=1-{\frac {1}{ln(S)}}.$

Mit der Definition des Parameters $s:=ln(S)*ln(n)^{-1/2}$ ergibt sich für große Werte von n für die Wahrscheinlichkeit glatte Relationen zu erhalten $P=exp(-1/s^{2})$. Aus der Definition des Parameters s folgt für die Schranke $S=\exp(s*{\ln(n)}^{1/2})$.

Die Laufzeit ist näherungsweise proportional $S^{2}/P$. Als Funktion des Parameters s erhalten wir ein Minmum für den Wert $s={ln(n)}^{-1/6}$. Damit erhalten wir schließlich

$S=\exp({ln(n)}^{1/3})$

und die Laufzeit für diese Wahl von S ist proportional ${S}^{3}=\exp(3*{ln(n)}^{1/3})$. Der Wert n ist hier kleiner als die letztlich zu faktorisierende Zahl N=PQ.

Diese Abschätzung der Komplexität beruht auf einigen nicht ganz zutreffenden Modellannahmen und ist daher mit einer gewissen Unsicherheit behaftet. Das Ergebnis deutet aber an, dass die Abschätzung von Pommerance die Laufzeit weit überschätzt. Insbesondere scheint der Wert für die vermeintlich optimale Schranke S viel zu hoch angesetzt.

Benutzer:Fsswsb 24.04

Erklärung für Nicht-Mathematiker

Der Artikel in seiner jetzigen Form ist leider für eine Enzyklopädie völlig ungeeigent. Ohne mathematische Vorkenntnisse, ist er einfach nicht verdaulich.

Die Idee hinter dem Verfahren ist jedoch sehr einfach und mit wenigen Grundkenntnissen in Mathematik verständlich. Alle Verfahren zur Faktorisierung großer Zahlen basieren auf einer Idee, die schon im 17. Jahrhundert von Fermat benutzt wurde. Fermat versuchte Faktoren einer Zahl n zu finden, indem er diese Zahl als Differenz zweier Qudrate darstellte.

Als Beispiel betrachten wir die Zahl 161. Zunächst berechnen wir die Wurzel aus 161 und erhalten den Wert 12,7. Jetzt bilden wir für die kleinsten ganzen Zahlen größer als 12, die Differenz des Quadrats und 161. Ist das Ergebnis eine Quadratzahl, kann 161 als Differenz zweier Quadrate geschrieben werden.

• 13*13 - 161 = 8 = 2*2*2
• 14*14 - 161 = 35 = 7*5
• 15*15 - 161 = 64 = (2*2*2)*(2*2*2)

Bereits in dritten Versuch haben wir eine Differenz von Quadratzahlen gefunden, die 161 ergibt. 161 = 15*15 - 8*8 = (15-8)*(15+8) = 7 * 23. Damit haben wir die Primfaktorenzerlegung der Zahl 161 gefunden.

Das Produkt zweier Primzahlen größer als 2, wie sie bei RSA verwendet werden, kann immer als die Differenz zweier Quadrate, hier von 15 und 8, geschrieben werden. Diese Zahlen sind die halbe Summe und die halbe Differenz der Zahlen p und q.

Zwei Quadratzahlen, die zur Faktorisierung dienen, können häufig schneller gefunden werden, wenn das Produkt mehrerer Zahlen auf der rechten Seite, hier 8, 35, 64, eine Quadratzahl ergibt. Damit ist das gundlegende Prinzip aller effizienten Verfahren zur Berechnung der Primfaktoren bereits erklärt. Zahlen mit 100 bis 200 Stellen, können damit faktorisiert werden.

Sicherheit von RSA

Effiziente Methoden zur Faktorsierung von 100-stelligen und größeren Zahlen haben praktisch nur diesen einen Hintergrund: RSA, ein kryptographisches Verfahren, das z.B. für die digitale Signatur eingesetzt wurde (und wird ?). Die Sicherheit dieses Verfahren beruht darauf, dass es praktisch unmöglich sein sollte, derartige Zahlen in Ihre Primfaktoren zu zerlegen. Diese Annahme ist jedoch zumindest für "nur" 200-stellige Zahlen offenkundig falsch.

Es ist nicht ganz eindeutig seit wann diese Tatsache allgemein bekannt war und welche Verfahren zur Faktorisierung dafür geeigent sind. Nach offizieller Darstellung ist das Quadratische Sieb nur für bis zu 129-stellige Zahlen geeignet. Nach meinen Überlegungen sollte es jedoch auch möglich sein größere Zahlen mit diesem Verfahren zu faktorisieren.

Extrem verwunderlich ist in diesem Zusammenhang, dass dieses Verfahren bereits 1981 entwickelt worden sein soll. Zu diesem Zeitpunkt galt die Faktorisierung einer 100-stelligen Zahl noch als faktisch ausgeschlossen. Erst etwa ein Jahrzehnt später wurde bekannt, dass 100-stellige Zahlen doch faktorisiert werden können. Dannach wurden 150-stellige Zahlen als nicht faktorisierbar erklärt, bis das Gegenteil 1999 belegt wurde. Jetzt gelten 300-stellige Zahlen als nicht faktorisierbar.

Die "Veröffentlichungen", die es zu diesem Thema gibt und mir zugänglich sind, wirken kaum wie seriöse wissenschaftliche Arbeiten. Ich hatte mal versucht die merkwürdigen Andeutungen, z.B. in dem Werk von Pommerance, zu verstehen und hier verständlich aufzuschreiben. Nach meinem Eindruck enthalten diese Arbeiten trotz einiger Merkwürdigkeiten viele Fakten, die aber nur seltsam verschleiert dargestellt werden.

Franz Scheerer

Was ist Fakt

Fakt ist vor allem eines

• RSA 640 is factoed!
• RSA 200 is factoed!
• RSA 576 is factoed!
• RSA 160 is factoed!
• RSA 155 is factoed!
• RSA 140 is factoed!

was unter http://www.rsasecurity.com/rsalabs/node.asp?id=2093 nachzulesen ist. Es sind ausnahmslos alle RSA-Challenges bis zu einer Größe von 200 Dezimalstellen faktorisiert. Die größeren Zahlen geben die Zahl der Stellen im Dualsystem an. Fakt ist weiterhin, dass dies in den 80-er Jahren für alle diese Zahlen als faktisch als ausgeschlossen galt. Selbst für eine nur 100-stellige Zahl sollte dies nach damaligen Schätzungen von einer Million bis Quatrillionen Jahre erfordern.

Es kann nicht eindeutig festgestellt werden, ob auch bereits größere Zahlen faktorisiert oder die Faktorisierung in Wahrheit nicht bereits früher erfolgte. Mit welchen Verfahren, in welcher Zeit, mit welchem Rechenaufwand, mit welcher Hardware und Software die Faktorisierung jeweils erfolgte, ist weniger eindeutig. Ich sehe zumindest nicht, wie diese Angaben auf ihre Richtigkeit geprüft werden sollten. Die Beschreibung der Algorithmen, die zu den jeweiligen Faktorisierungen verwendet wurden, beschränkt sich meist auf einige Schlagworte und eine mehr oder minder fantasievolle Bezeichnung des Verfahrens.

Die Abschätzungen über die asymmtotische Laufzeit sind daher in keiner Weise nachvollziehbar. Die Frage wie sich die Laufzeit eines solchen Verfahrens für beliebig große Zahlen verhält erscheint mir ohnehin von eher geringem Interesse. Interessanter wäre die Frage, mit welchem Aufwand heute übliche RSA-Module faktorisiert werden könnten. Dazu gibt es aus meiner Sicht keine glaubhaften Angaben. Warum sollte die Faktorisierung einer 212-stelligen Zahl weit aus schwieriger sein, als die Faktorisierung einer 200-stelligen.

Zur Faktorisierung von RSA-200 wird ein Rechenaufwand von unter 200 GHz-Jahren angegeben. Dies entspricht in etwa 200 GFLOPS-Jahre. Ein moderner Supercomputer könnte einen solchen Rechenaufwand in wenigen Tagen bewältigen. Franz Scheerer