Diskussion:Quadratisches Sieb

Diskussion:Quadratisches Sieb/Archiv

Diskussion:Quadratisches Sieb

ich schreibe zur zeit an einer diploamrebit zum thema faktorisierung und weil die diplomarbeit von schmidt-samoa hier fehl am platz ist, habe ich sie zum nfs verschoben, wo sie hingehört. wozu wird das jetzt wieder hergestellt? die quelle ist falsch da qs nicht gleich nfs.

Ja die Arbeit zielt auf das NFS ab, aber es werden auch die grundlegenden Gedanken des Quadratischen Siebs erklärt. Warum nicht bei beiden Thema zitieren, da die Arbeit doch ziemlich qualifiziert ist. Aber wenn du es hier nicht erwähnen willst, soll mir es auch Recht sein.--ThiloHarich 13:43, 24. Aug. 2007 (CEST)

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

Siebschritt

Im Abschnitt "Siebschritt" steht: "Um effizient zu überprüfen, ob eine Zahl glatt ist, benutzt man folgende Eigenschaft: ..." und dann einige Formeln, die wenn ich das richtig sehe zunächst nur Umformungen des Grundterms $q(x+kp)$ sind, um die eigentliche Aussage, nämlich $q(x+kp)\equiv q(x){\pmod {p}}$ herzuleiten. Ich denke wenn, dann wäre es besser das ganze in eine Matheumgebung zu packen, am Gleichheitszeichen auszurichten und $q(x+kp)$ am Anfang wegzulassen (oder einfach die Zwischenschritte ganz weglassen, ich finde das muss in ein Nachschlagewerk nicht unbedingt rein...). --Xlae 15:53, 1. Sep. 2008 (CEST)

Erledigt. --Stefan Birkner 19:53, 1. Sep. 2008 (CEST)

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)

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 meisten glatten Zahlen enthalten jedoch Quadrate und eventuell sogar höhere Potenzen der kleinen Primzahlen." Das mag für kleinere Faktoren stimmen (manche Implementierungen sieben hier auch wirklich mit den Potenzen), bei den meisten (größeren) Faktoren der Faktorbasis stimmt das nicht. Das Sieben mit Quadraten liefert weniger glatte Relationen (es werden ja pro Faktor nur noch Wurzel der normalen Stellen gestrichen). Das MPQS verwendet z.B. ein Quadrat (wenngleich in einer etwas anderen Form). Verwendet man aber statt dessen (einfache) Faktoren der Faktorbasis (SIQS) so findet man mehr glatte Relationen.--ThiloHarich 13:56, 24. Aug. 2007 (CEST)

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.

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.

Die ggT Methode arbeitet nur dann schnell, wenn die Multiplikation schnell ist. Bei der Schulmethode kommt man auf einen quadratischen Aufwand, was in diesem Fall der Probedivision entspricht. Bernstein verwendet die schnelle Fourier Transformation zur Multiplikation. Dann lohnt sich das.--ThiloHarich 14:03, 24. Aug. 2007 (CEST)

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.

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

Ja die Probedivision braucht quadratisch so viel Zeit wie die Pollard-Rho-Methode. Werde die Pollard-Rho-Methodein meiner Implementierung mal einbauen. Damit die ggT Methode schneller ist als Pollard-Rho braucht man eine Multiplikationseinheit, die in O(n^1.5) multiplizieren kann. Ach ja am Bestem Man unterschreibt seine Diskusinsbeiträge mit --(vier mal)~ (das zweitrechteste Icon über dem Eingabebereich. --ThiloHarich 14:37, 24. Aug. 2007 (CEST)

Die Pollard-Rho-Methode ist in der Praxis langsamer als (eine Variante der) Probedivision. Man wendet nicht wirklich die Probedivision an. Da man für das Sieben ja bereits zu jedem Faktor der Faktorbasis die Stellen des Polynoms bestimmt hat, bei dem diese durch die den Faktor teilbar sind checkt man einfach, ob die vermutlich glatte Zahl diesen Stellen entspricht. Dieses Verfahren arbeitet unabhänig von der Größe der zu prüfenden Zahl. Sowohl Pollard-Rho als auch die normale Probedivision rechnen ja mit dieser Zahl, die meisstens nicht in ein Systemregister passt.--ThiloHarich 15:06, 19. Sep. 2007 (CEST)

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.

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)

Das mit dem Vorfaktor kann man natürlich in den Artikel schreiben.--ThiloHarich 14:43, 24. Aug. 2007 (CEST)

Funktionsweise - Auf Grund der 3. Binomischen Formel gilt

In der Funktionsweise steht zwar Auf Grund der 3. Binomischen Formel gilt, was auch richtig ist. In der nachfolgenden Rechnung allerdings, wird der Sachverhalt komplett ohne die dritte Binomische Formel gezeigt. Ich wäre dafür entweder beide Herleitungen zu zeigen oder die Bemerkung zu entfernen. --Jobu0101 19:25, 20. Feb. 2010 (CET)

Habs gekürzt, da die Darstellung wohl eher verwirrt.--ThiloHarich 17:06, 21. Feb. 2010 (CET)

Implementierungen

Hallo zusammen, ich habe mal mein neues PSIQS-Paket zu den Implementierungen hinzugefügt. Es sind das original QS, MPQS und SIQS enthalten, letzteres auch in einer parallelisierten Version. Ich wollte auf der Hauptseite aber nicht zu viel Text schreiben ;) Ich denke dass der Sourcecode gut verständlich ist. MfG Tilman Neumann 93.193.186.99 15:04, 15. Jan. 2016 (CET)

Mehrfache Polynome

Im Abschnitt zu mehreren Polynomen (vorletzter Absatz) steht "Beim Multiple Polynomial Quadratic Sieve (MPQS) wählt man a als Quadrat einer Primzahl so n ein quadratischer Rest mod 4a" ist. Woher kommt der Faktor 4? Das wird mir an dieser Stelle nicht klar. Ist evt. doch an der Stelle gemeint, dass a so gewählt wird, dass n ein quadratischer Rest mod a ist?

Nachtrag: Zumal Q(x) ja u.a. durch 4 bzw. dann 2 teilbar ist. Aber n muss ja kein quadratischer Resto mod 2 sein. Hier wird m.E. bereits Gedanken aus dem Abschnitt zu Vorfaktoren voraus gesetzt aber ohne auf diese einzugehen.

Q(x) = (a*x+b)^2 - N ist nur durch "a" teilbar. Aber Q2(x) = (2*a*x+b)^2 - N ist durch "4a" teilbar wenn b ungerade ist. Falls im zweiten Fall mit Knuth-Schroeppel-multipliern k gearbeitet wird (dann Q2(x) = (2*a*x+b)^2 - kN), muss außerdem kN == 1 (mod 8) erfüllt sein. Der Artikel bezieht sich anscheinend auf Referenzen, die teilweise Q(x) und teilweise Q2(x) verwenden. Tilman Neumann 89.182.182.142 23:42, 23. Feb. 2018 (CET)

Mathematics of Computation ist auf ams.org nahezu komplett im Fulltext einsehbar

ab Nr. 1, bis auf ca. die letzten 5 Jahre. Traugott (Diskussion) 21:22, 14. Jun. 2020 (CEST)

Mehrere Anmerkungen

1.: (Abschnitt "Funktionsweise"):

Am Anfang des Abschnitts wird die "Darstellung als Differenz von Quadraten" zweimal genannt, ich denke einmal sollte reichen. Hingegen wird bei der Setzung, n solle die zu faktorisierende Zahl sein, angenommen, der Leser habe sie noch aus dem einleitenden Kapitel im Gedächtnis.

2.: (Abschnitt "Partielle Relationen"):

Außer dieser in der Literatur auch so genannten large prime variation gibt es noch die two large primes variation, die auch fastglatte Relationen mit zwei großen Primfaktoren P_1 und P_2 sammelt und diese dann mithilfe eines graphentheoretischen Wege- und Kreise- Such- Algorithmus zu glatten Relationen kombiniert. Dies hat dann allerdings den Nachteil, dass die riesige Matrix am Ende nicht mehr sparse (dünn besetzt) ist.

Es gibt auch eine Varinante, die drei große Primzahlen außerhalb der Faktorbasis zu glatten Relationen kombiniert: https://www.mersenneforum.org/showthread.php?t=25676 das macht bei 140 Stellen also mehr als 400 bit wohl Sinn. Ich wollte nicht alle Feinheiten in den Artikel packen. Aber kann ja gerne ergänzt werden.--ThiloHarich (Diskussion) 22:08, 24. Sep. 2020 (CEST)

3.: (Abschnitt "Mehrfache Polynome"):

Hier steht der Satz  „Beim Multiple Polynomial Quadratic Sieve (MPQS) wählt man {\displaystyle a} als Quadrat einer Primzahl so dass {\displaystyle n} ein quadratischer Rest mod {\displaystyle 4a} ist.“  Sowohl ein Komma vor dem „so dass“ als auch ein Komma zwischen „so“" und „dass“ ergeben einen grammatikalisch korrekten deutschen Satz, aber die beiden Sätze unterscheiden sich inhaltlich. Welcher ist gemeint?

Komma nach dem so --ThiloHarich (Diskussion) 22:08, 24. Sep. 2020 (CEST)

4.: Es gibt einen weiteren möglichen Grund, die Suchschranke T zu erhöhen: Das Sieben mit den besonders kleinen Elementen der Faktorbasis ist aufwendiger als das Sieben mit den größeren Elementen, und es bringt tendenziell weniger ein. Stattdessen kann man es zunächst bleiben lassen und dann nach dem allgemeinen Sieben die aussichtsreichen Kandidaten mit Probedivision durch die kleinen Elemente (und ihre Potenzen!) prüfen.

In der Praxis verzichtet man auf das teure Sieben mit den kleinen Zahlen, und erhöht die Suchschranke. Man kann zu einem kleinen Produkt der Zahlen der Faktorbasis auch die Faktoren innerhalb dieses Bereichs bestimmen und das Siebarray mit den Längen der Faktorisierungen über dieser Faktorbasis initialisieren. Generell versucht man nur mit den Zahlen in der mittleren Bereich der Faktorbasis zu sieben. Man kann auch mit Potenzen sieben, bringt in der Praxis aber wohl nichts.--ThiloHarich (Diskussion) 22:08, 24. Sep. 2020 (CEST)

--Himbeerbläuling (Diskussion) 14:00, 20. Sep. 2020 (CEST)

Wow, Danke. 3LP variation war jetzt echt 'ne Überraschung, hatte ich nicht mit gerechnet dass man da Relationen draus machen kann. Gibt es da einen Link zu einem Text, der das erklärt? --Himbeerbläuling (Diskussion) 20:01, 26. Sep. 2020 (CEST)

Hier ist die Idee mit dem Graphen für zwei große Primzahlen außerhalb der Faktorbasis erklärt: https://projecteuclid.org/download/pdf_1/euclid.em/1047565445. Und hier noch mal detaillierter für drei. Ist aber das gleiche Prinzip: https://www.researchgate.net/publication/221451526_MPQS_with_three_large_primes --ThiloHarich. Wie im Mersenne forum diskutiert, ist dies wohl schneller als das Zahlenkörpersieb für eine doch beträchtliche Zahlengröße. (Diskussion) 17:54, 1. Okt. 2020 (CEST)

Danke. --Himbeerbläuling (Diskussion) 21:45, 2. Okt. 2020 (CEST)