Diskussion:Quadratisches Sieb

aus Wikipedia, der freien Enzyklopädie

Diskussion:Quadratisches Sieb/Archiv

Ich habe mal die nicht so qualifizierten Beiträge entfernt, und ältere interessante Beiträge ergänzt.--ThiloHarich 14:40, 15. Jan. 2007 (CET)

Inhaltsverzeichnis 1 Beispiel 2 Neues Siebkriterium 3 Die ggT-Methode 4 Pollard-Rho-Methode oder Rekursion 5 Weitere Relationen Q(kn)

[Bearbeiten] Beispiel

Hat jemand ein gutes Beispiel für das QS? Also mit einer Faktorbasis der Länge ca. 4 bzw. 5 bei der die Lösung nicht offensichtlich ist, und bei der die Grundprinzipien gut raus kommen?--ThiloHarich 14:44, 15. Jan. 2007 (CET)

[Bearbeiten] 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², so können durch Addition Viefacher von p² leicht weitere Q(k) mit dieser Quadratzahl als Faktor gefunden werden. Suchen wir nach denjenigen Q(k) mit p² 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.

[Bearbeiten] 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₁,p₂,...,p_n geschrieben werden kann lässt sich in der Form

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.

Dieses Verfahren wurde von Daniel Bernstein u.a. http://cr.yp.to/factorization/smoothparts-20040510.pdf weiter verbessert. Ich vermute es wurde bei der Faktorisierung von RSA-200 http://www.crypto-world.com/announcements/rsa200.txt eingesetzt.

[Bearbeiten] 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 . 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⁶ 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.

Bernstein schreibt sein Verfahren sei schneller.--ThiloHarich 14:41, 15. Jan. 2007 (CET)

[Bearbeiten] Weitere Relationen Q(kn)

Es bietet sich an statt der Relationen Q(x) = x² − n weitere der Form 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 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= und für einen Wert k zu betrachten.

Diese Vorfaktoren werden in der Praxis eingesetzt, und können leicht (im Vergleich zum restlichen Laufzeit) bestimmt werden. Sie können den Algorithmus um einen konstanten Faktor beschleunigen. Der Faktor scheint jedoch nur sehr selten größer als 2 zu sein.--ThiloHarich 14:44, 15. Jan. 2007 (CET)