Quadratisches Sieb

Quadratisches Sieb ist ein Begriff aus dem Bereich Zahlentheorie der Mathematik und bezeichnet einen der schnellsten bekannten Algorithmen zur Faktorisierung großer natürlicher Zahlen. Es ist ein allgemeines Faktorisierungsverfahren, d. h. die Laufzeit hängt nur von der Größe der zu faktorisierenden Zahl ab und nicht von speziellen Eigenschaften der Zahl (bzw. ihrer Teiler). Für Zahlen mit bis ca. 100 Dezimalstellen ist es das schnellste (allgemeine) Faktorisierungsverfahren. Für größere Zahlen ist das Zahlkörpersieb schneller. Die Laufzeit zum Faktorisieren einer Zahl n mit dem quadratischen Sieb ist (unter einigen als wahrscheinlich geltenden Annahmen) in der Größenordnung von

$\exp \left({\sqrt {\ln n\cdot \ln \ln n}}\right).$

Entstehungsgeschichte

Aufbauend auf der Kettenbruchmethode von John Brillhart und Michael Morrison sowie inspiriert durch das lineare Sieb von Richard Schroeppel erfand Carl Pomerance 1981 durch theoretische Überlegungen das Quadratische Sieb, welches schneller war als alle bis dahin bekannten Faktorisierungsverfahren.

Kurz darauf fanden James Davis und Diane Holdridge bzw. Peter Montgomery unabhängig voneinander eine Variante des Quadratischen Siebs mit mehrfachen Polynomen (genannt MPQS). Eine andere Verbesserung, das sogenannte spezielle quadratische Sieb, stammt von Mingzhi Zhang; es kann aber nur auf spezielle Zahlen angewandt werden.

1994 gelang es, mit Hilfe des Quadratischen Siebs die 129-stellige Zahl RSA-129 zu faktorisieren.

Mehr zur Geschichte des Quadratischen Siebs findet sich im Artikel Geschichte der Faktorisierungsverfahren.

Funktionsweise

Das Quadratische Sieb ist eine Weiterentwicklung von Dixons Faktorisierungsmethode. Wie die meisten modernen Faktorisierungsverfahren benutzt es die Darstellung eines Produkts als Differenz von Quadraten. Auf Grund der 3. Binomischen Formel gilt:

$x^{2}-y^{2}=(x+y)\cdot (x-y)=n$

Anstatt die Teilbarkeit einer Zahl zu untersuchen, sucht man eine Darstellung der Zahl als Differenz von Quadraten. Aus einer Darstellung $x^{2}-n=y^{2}$ erhält man die Teiler $x+y$ sowie $x-y$ von $n$.

Bei der Faktorisierungsmethode von Fermat berechnet man den Wert $q(x)=x^{2}-n$ für verschiedene Zahlen $x$, bis man ein $q(x)$ erhält, das eine Quadratzahl ist. Als erstes $x$ wählt man die kleinste Zahl, die größer als die Wurzel von $n$ ist. Anschließend zählt man $x$ in jedem Schritt um eins hoch. Wendet man dieses Verfahren beispielsweise zur Faktorisierung der Zahl 1649 an, so erhält man für $q(x)$ die Werte in der folgenden Tabelle.

$x$	$q(x)=x^{2}-n$	Primfaktorzerlegung von $q(x)$
41	32	25
42	115	5 · 23
43	200	23·52
	…
57	1600	402

Die Faktorisierungsmethode von Fermat gelangt nach 16 Schritten zum Ziel und kann dann anhand der Zahl $x=57$ und des Quadrats $q(x)=40^{2}$ die Faktorisierung von $1649$ berechnen:

$1649=57^{2}-40^{2}=(57+40)\cdot (57-40)=97\cdot 17$

Wenn man die Funktionswerte zu $x=41$ und $x=43$ miteinander multipliziert, erhält man das Quadrat $2^{5}\cdot 2^{3}\cdot 5^{2}=2^{8}\cdot 5^{2}=(2^{4}\cdot 5)^{2}$. Man würde dieses Quadrat gerne für eine Zerlegung nutzen. Die beiden Gleichungen können jedoch nicht ohne weiteres multipliziert werden. Maurice Kraitchik erweiterte die Darstellung von Fermat. Er betrachtete Gleichungen, in denen $x^{2}-y^{2}$ ein Vielfaches von $n$ ist:

$n|x^{2}-y^{2}\Leftrightarrow n|(x+y)(x-y)$

Falls $n|(x+y)(x-y)$, aber $n$ weder $x+y$ noch $x-y$ teilt, dann gilt (für den größten gemeinsamer Teiler) $\operatorname {ggT} (x+y,n)>1$ und $\operatorname {ggT} (x+y,n)$ ist ein nichttrivialer Teiler von $n$. Anstatt der Gleichung $q(x)=x^{2}-n$ betrachtet man folgende Kongruenzen:

$n|x^{2}-q(x)\Leftrightarrow x^{2}\equiv q(x){\pmod {n}}$

Diese Kongruenzen können nun multipliziert werden. Wenn man die Kongruenz zu $x=41$

$41^{2}\equiv 2^{5}{\pmod {1649}}$

und $x=43$

$43^{2}\equiv 2^{3}\cdot 5^{2}{\pmod {1649}}$ multipliziert, erhält man folgende Kongruenz

$41^{2}\cdot 43^{2}\equiv 2^{5}\cdot 2^{3}\cdot 5^{2}{\pmod {1649}}$.

Man hat folgende quadratische Kongruenz gefunden:

$(41\cdot 43)^{2}\equiv (2^{4}\cdot 5)^{2}{\pmod {1649}}$.

Mit $\operatorname {ggT} (41\cdot 43-80,1649)=17$ und $\operatorname {ggT} (41\cdot 43+80,1649)=97$ hat man $1649=17\cdot 97$ in seine Faktoren zerlegt. Nicht jede quadratische Kongruenz liefert echte Teiler, aber im Schnitt liefert jede zweite quadratische Kongruenz eine echte Faktorisierung. Man muss nun viel weniger Funktionswerte von $q(x)$ betrachten, um ein Quadrat und damit eine Zerlegung zu erhalten. Wie kann man effizient bestimmen, welche Funktionswerte sich zu einem Quadrat aufmultiplizieren? Falls man die Primfaktorzerlegung der Zahlen $q(x)$ kennt, wird die Multiplikation dieser Zahlen zur Addition der Exponenten ihrer Primfaktorzerlegung. Man betrachtet deswegen nur glatte Zahlen $q(x)$, deren Primfaktorzerlegung aus vorher festgelegten Faktoren bestehen. Eine Kongruenz ist genau dann ein Quadrat, wenn die Exponenten der Primfaktorzerlegung gerade sind. Unter diesen Einschränkungen kann man die Kongruenzen, die sich zu einem Quadrat multiplizieren, mittels Methoden aus der linearen Algebra bestimmen.

Im Allgemeinen sucht man in einer ersten Phase nach Kongruenzen. Hat man ausreichend viele gefunden, wird eine Teilmenge von Kongruenzen gesucht, die, miteinander multipliziert, auf beiden Seiten ein Quadrat ergeben.

Gesucht sei die Primfaktorzerlegung von $n=87463$. Man betrachtet nur Zahlen $x^{2}-n$, die aus kleinen Faktoren bestehen. Sei der größte Primfaktor $29$. Da $x^{2}=n\mod p$ für $p=5,7,11$ und $23$ keine Lösung hat, kommen diese Zahlen niemals als Teiler von $x^{2}-n$ vor. Die sogenannte Faktorbasis, in der alle möglichen Faktoren der Primfaktorzerlegung vorkommen, besteht also aus den Primzahlen $2,3,13,17,19,29$. Die Matrix der Exponenten der Primfaktorzerlegung $\mod {2}$ sieht wie folgt aus:

x	q(x) = x2-n	Primfaktorzerlegung								Primfaktorzerlegung mod 2
		-1	2	3	13	17	19	29		-1	2	3	13	17	19	29
265	-1 · 2 · 3 · 132 · 17	1	1	1	2	1	0	0		1	1	1	0	1	0	0
278	-1 · 33 · 13 · 29	1	0	3	1	0	0	1		1	0	1	1	0	0	1
296	32 · 17	0	0	2	0	1	0	0		0	0	0	0	1	0	0
299	2 · 3 · 17 · 19	0	1	1	0	1	1	0		0	1	1	0	1	1	0
307	2 · 32 · 13 · 29	0	1	2	1	0	0	1		0	1	0	1	0	0	1
316	36 · 17	0	0	6	0	1	0	0		0	0	0	0	1	0	0

Gesucht ist eine Linearkombination der Zeilen, die den Nullvektor ergeben. Eine Lösung besteht aus Zeile 3 und Zeile 6.

$x=296\cdot 316=93536\equiv 6073{\pmod {n}}$

$y={\sqrt {3^{2}\cdot 17\cdot 3^{6}\cdot 17}}=3^{4}\cdot 17=1377\equiv 1377{\pmod {n}}$

$\operatorname {ggT} (x-y,n)=587$, $\operatorname {ggT} (x+y,n)=149$. Damit erhält man die Faktorisierung $87463=587\cdot 149$.

Diese Grundidee wird auch in Dixons Sieb verwendet, wo man zufällige Werte für x verwendet. Im Quadratischen Sieb betrachtet man aufeinanderfolgende Werte x, von denen man die Primfaktorzerlegung schnell bestimmen kann. Das Bestimmen solcher nützlicher Kongruenzen nennt man Sieben. Der Algorithmus lässt sich in zwei Schritte aufteilen:

1. der Siebschritt, bei dem Kongruenzen der Form $x^{2}=q{\pmod {n}}$ gesucht werden, und
2. der Auswahlschritt, bei dem aus diesen Kongruenzen geeignete ausgewählt werden, aus denen sich durch Multiplikation eine quadratische Kongruenz ergibt.

Siebschritt

Im Siebschritt werden Kongruenzen der Form

$x^{2}\equiv q\mod n$

gesucht, wobei die Primfaktorzerlegung von q bekannt ist und nur aus kleinen Primzahlen besteht (in anderen Worten: q soll bezüglich einer festen Schranke glatt sein). Man wählt die Zahlen x in der Nähe der Wurzel von n, damit sind die Werte $q(x):=x^{2}-n$ klein. Die Wahrscheinlichkeit, glatte Zahlen q(x) zu finden, ist damit hoch. Allerdings ist die Primfaktorzerlegung einer Zahl im Allgemeinen nicht in Polynomialzeit berechenbar. Um dennoch effizient zu überprüfen, ob eine Zahl glatt ist, benutzt man folgende Eigenschaft:

${\begin{aligned}q(x)&=x^{2}-n\\q(x+kp)&=(x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=q(x)+2xkp+(kp)^{2}\\&\equiv q(x){\pmod {p}}\end{aligned}}$

Wenn man also Stellen x gefunden hat, bei denen q(x) durch p teilbar ist, kann man eine ganze Sequenz von $q(x+kp)$ bestimmen, die durch p teilbar sind. p teilt $q(x)=x^{2}-n$ genau dann, wenn $x^{2}\equiv n{\pmod {p}}$. Das Bestimmen der Quadratischen Wurzeln modulo einer Primzahl ist effizient lösbar (etwa mittels des Shanks-Tonelli Algorithmus). Die Sequenz der ebenfalls durch p teilbaren Zahlen wird mit einem Siebverfahren ähnlich dem des Sieb des Eratosthenes bestimmt. Das Quadratische Sieb leitet seinen Namen vom Lösen der 'Quadratischen' Gleichung und dem 'Sieben' der Teiler ab.

Für $n=221$ werden die Bilder der Elemente $\{1\ldots 15\}$ unter der Funktion $f(x)=x^{2}-n$ auf Teilbarkeit durch ${\textstyle 5}$ getestet. Dabei kann von den beiden ersten Zahlen auf die jeweils nächsten geschlossen werden.

Im Prinzip geht man wie folgt vor:

Schritt 1: Wahl einer Faktorbasis. Nimm alle Primzahlen p bis zu einer Schranke S, für die n quadratischer Rest ist, d. h. die Gleichung $x^{2}=n{\pmod {p}}$ lösbar ist. Zahlen, für die n quadratischer Nichtrest ist, können ausgeschlossen werden, da sie nicht als Teiler von $x^{2}-n$ auftreten. Je größer die Schranke gewählt wird, umso größer die Wahrscheinlichkeit, dass $x^{2}-n$ nur aus Primfaktoren bis zu dieser Schranke besteht. Der Nachteil ist, dass man mehr Relationen braucht um das resultierende Gleichungssystem zu lösen. Wird die Schranke zu klein gewählt, zerfallen nur sehr wenige Zahlen wie gewünscht und wir müssen viele Zahlen betrachten. Deshalb wählt man die Schranke S in der Größenordnung von $S:={\sqrt {\exp \left({\sqrt {\ln n\ln \ln n}}\right)}}$ Schritt 2: Siebe mit den Faktoren der Faktorbasis. Wähle ein Siebintervall in der Größenordnung von $L:=S^{2}=\exp \left({\sqrt {\ln n\ln \ln n}}\right)$. Für die Zahlen x mit |x - √n| < L fertige eine Liste mit den Werten $q(x):=x^{2}-n$ an. Bestimme die (zwei) Lösungen von $q(t)=0\mod p$ für alle Faktoren p der Faktorbasis. Teile alle Zahlen $q(t+k\cdot p)$ innerhalb eines gewählten Siebintervalls durch p (sowie p2, p3, …). Die Zahlen, bei denen am Ende eine 1 übrig bleibt, sind glatt bezüglich der Faktorbasis und damit die gesuchten Werte.

Die zu untersuchenden Zahlen q(x) sind in der Größenordnung von n. Divisionen auf diesen Zahlen sind teuer (für typische n sind diese nicht mehr in hardwarenahen Formaten speicherbar). Da das Sieben laufzeitkritisch ist, modifiziert man Schritt 2. Man speichert nicht die Zahlen q(x) selbst, sondern deren auf ganze Zahlen gerundete Logarithmen (bzw. n als obere Schranke für q(x)). Diese kleinen Zahlen können mit primitiven Datentypen behandelt werden. Aus der Division durch einen Teiler p wird eine Subtraktion mit dem Logarithmus von p. Aus Geschwindigkeitsgründen verzichtet man in der Praxis auch auf das Sieben mit Potenzen der Faktoren.

Man schätzt die Rechenfehler (und das Ignorieren mehrfacher Teiler) durch eine Schranke T in der Größenordnung des Logarithmus des größten Faktors der Faktorbasis ab. Die Zahlen aus der Liste, die nach dem Sieben kleiner als T sind, sind mit hoher Wahrscheinlichkeit glatt und werden in einer Liste vermerkt. Nicht alle in der Liste vermerkten Zahlen sind notwendigerweise glatt. In einem zusätzlichen Schritt wird die Primfaktorzerlegung dieser Zahlen bestimmt und vermerkt, ob die Zahl glatt ist oder nicht.

Das Bestimmen der Primfaktorzerlegung der wahrscheinlich glatten Zahlen über der Faktorbasis kann man mit einem Faktorisierungsverfahren erledigen, das für Faktoren dieser Größe geeignet ist. Für kleine Faktoren bietet sich die Pollard-Rho-Methode an. Eine andere Methode besteht darin, ein zweites Mal zu sieben. Trifft man dabei auf eine wahrscheinlich glatte Zahl, so teilt man diese durch den Faktor, mit dem man siebt, bzw. deren Potenzen. Da die Trefferrate für große Faktoren gering ist, bietet sich dies für die größeren Faktoren der Faktorbasis an. Das Sieben kann weiter beschleunigt werden, wenn man den ggT der zu testenden Zahl mit dem Produkt der Faktoren der Faktorbasis bestimmt.

Auswahlschritt

Zu einer (glatten) Kongruenz $x^{2}\equiv q{\pmod {n}}$ besteht q nur aus Faktoren der Faktorbasis. q kann vollständig als Vektor der Exponenten seiner bekannten Primfaktorzerlegung beschrieben werden. Zu den Exponentenvektoren der Kongruenzen stellt man ein lineares Gleichungssystem über dem endlichen Körper F₂ auf, bei dem jede Zeile aus dem Exponentenvektor einer Kongruenz modulo 2 besteht. Eine Zahl ist genau dann ein Quadrat, wenn alle Exponenten ihrer Primfaktorzerlegung gerade sind. Falls man also eine nichttriviale Linearkombination von Zeilen findet, die den Nullvektor ergeben, hat man auch eine quadratische Kongruenz gefunden. Sie liefert durch Berechnung des größten gemeinsamer Teilers $\operatorname {ggT} (u-v,n)$ einen Faktor von n, der in mindestens der Hälfte aller Fälle weder 1 noch n ist.

Zur Lösung dieses Schritts verwendet man Verfahren der linearen Algebra, wie das gaußsche Eliminationsverfahren, das Verfahren der konjugierten Gradienten oder das Lanczos-Verfahren. Das Block Lanczos-Verfahren, eine Erweiterung des Lanczos-Verfahrens, kann solche großen – aber sehr dünn besetzten – Matrizen in einem Bruchteil des Siebschritts Platz sparend (linear in der Anzahl der Zeilen) lösen.

Einsatzbereich

Das Quadratische Sieb eignet sich für große Zahlen bis etwa 110 Dezimalstellen, die keine Primpotenz sind. Für größere Zahlen ist das Zahlkörpersieb besser geeignet.

1994 wurde die Zahl RSA-129 mit dem Multiple Polynomial Quadratic Sieve unter Ausnutzung partieller Relationen faktorisiert. Diese Zahl mit 129 Dezimalstellen wurde in ihre zwei Teiler (einer mit 64, der andere mit 65 Dezimalstellen) zerlegt. Der Siebschritt wurde verteilt von 600 Freiwilligen ausgeführt. Diese sammelten 8 Monate lang Kongruenzen, die per E-Mail (oder ftp) an den zentralen Rechner übermittelt wurden. Der Auswahlschritt auf den 298 GB Daten wurde in 45 Stunden auf einem Supercomputer ausgeführt. Die Faktorbasis umfasste 524338 Primzahlen, die Matrix hatte eine Größe von 569466 Zeilen und 524338 Spalten.

Alle weiteren Faktorisierungsrekorde wurden mit dem Zahlkörpersieb aufgestellt.

Misst man die Laufzeit des Algorithmus bezüglich der Länge $N=\log(n)$ der Eingabe n, so kann man die Laufzeit des Quadratischen Siebs so schreiben:

$e^{c*{N^{\alpha }(\log N)^{1-\alpha }}},\alpha =1/2,c=1$

Für $\alpha =1$ ergibt sich ein exponentielles Wachstum. Die Probedivision hat ein solches Laufzeitverhalten für $c=1/2$. Mit $\alpha =0$ ergäbe sich ein polynomieller Algorithmus mit Laufzeit ${\mathcal {O}}(n^{c})$. Es handelt sich beim Quadratischen Sieb also um einen Algorithmus mit einer superpolynomialen, aber subexponentiellen Laufzeit. Beim Zahlenkörpersieb konnte die Konstante $\alpha$ auf 1/3 reduziert werden. Allerdings ist c, das die Laufzeit asymptotisch weniger beeinflusst als $\alpha$, dort wesentlich größer. Es gibt Verbesserungen der Grundidee des Quadratischen Siebs, die die Laufzeit weiter reduzieren:

Partielle Relationen

Selbst Relationen, die nicht glatt sind, können zu (glatten) Relationen kombiniert werden, die für den Auswahlschritt brauchbar sind. Hat man zwei partielle Relationen, deren Primfaktorzerlegung einen Faktor P (außerhalb der Faktorbasis) enthalten

$x^{2}\equiv p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdot \cdot \cdot p_{s}^{k_{s}}\cdot P{\pmod {n}}$

${\bar {x}}^{2}\equiv p_{1}^{l_{1}}\cdot p_{2}^{l_{2}}\cdot \cdot \cdot p_{s}^{l_{s}}\cdot P{\pmod {n}}$

so ergeben diese eine Kongruenz

$(x\cdot {\bar {x}})^{2}\equiv p_{1}^{k_{1}+l_{1}}\cdot p_{2}^{k_{2}+l_{2}}\cdot \cdot \cdot p_{s}^{k_{s}+l_{s}}\cdot P^{2}{\pmod {n}}$

Durch Multiplikation mit P⁻² erhält man sogar folgende glatte Relation

$(x\cdot {\bar {x}}\cdot P^{-1})^{2}\equiv p_{1}^{k_{1}+l_{1}}\cdot p_{2}^{k_{2}+l_{2}}\cdot \cdot \cdot p_{s}^{k_{s}+l_{s}}{\pmod {n}}$

Bei der vorletzten Relation stammen alle Faktoren mit ungeraden Exponenten aus der Faktorbasis. Diese Relation kann somit für den Auswahlschritt verwendet werden. Wenn man den Faktor $P$ in der Größe begrenzt, kann man ihn mit einem geringen Mehraufwand bestimmen: Man erhöht die Schranke $T$ für die interessanten Zahlen im Siebschritt um $\log(P)$. Der Faktor $P$ bleibt beim Bestimmen der Primfaktorzerlegung durch das Teilen mit Faktoren der Faktorbasis schließlich übrig. Durch partielle Relationen kann man die Anzahl der für den Auswahlschritt brauchbaren Relationen erhöhen. Die Laufzeit kann damit halbiert werden.

Mehrfache Polynome

Die Größe der erzeugten Zahlen beim Quadratischen Sieb steigt linear mit der Entfernung zur Nullstelle an. Beim Multiple Polynomial Quadratic Sieve (MPQS) definiert man verschiedene (möglichst disjunkte) Funktionen, die jeweils einen festen Faktor enthalten und dasselbe Wachstum zeigen. Das Suchintervall kann auf mehrere Polynome aufgeteilt werden. Damit sind die auf Teiler zu untersuchenden Zahlen kleiner und die Wahrscheinlichkeit, eine glatte Zahl zu erzeugen, steigt.

Man modifiziert die Funktion $q(x)=x^{2}-n$, indem man anstelle von $x$ nun ein Polynom ersten Grades verwendet.

Das Multiple Polynomial Quadratic Sieve betrachtet eine Menge von Polynomen

$q_{a}(x)=(2ax+b)^{2}-n$

Dabei wird $b$ so gewählt, dass $b^{2}-n$ durch $4a$ teilbar ist: $b^{2}-n=4ac$ . Damit gilt

$q_{a}(x)=(2ax+b)^{2}-n=(2ax)^{2}+4abx+b^{2}-n=4a\cdot (ax^{2}+bx+c)$

und der hiermit erzeugte Wert $q_{a}(x)$ enthält $4a$ als Faktor. Die Wahl von geraden Faktoren $2a$ erzeugt neben dem Faktor $2a$ einen zusätzlichen Faktor $2$ in den erzeugten Zahlen.

Beim Multiple Polynomial Quadratic Sieve (MPQS) wählt man $a$ als Quadrat einer Primzahl, so dass $n$ ein quadratischer Rest mod $4a$ ist. Damit hat die Gleichung $b^{2}=n\ mod\ a$ für $b$ genau zwei Lösungen und ist effizient bestimmbar. Das Verfahren wurde 1983 von J. A. Davis und D. B. Holdridge entwickelt. Der Siebvorgang selbst funktioniert ähnlich wie beim normalen Quadratischen Sieb, allerdings muss zu jedem Faktor $p$ der Faktorbasis das inverse Element von $a\ mod\ p$ berechnet werden, was einen großen Anteil an der Gesamtrechenzeit in Anspruch nimmt.

Beim Self Initializing Quadratic Sieve (SIQS) wird $a$ als Produkt von Faktoren der Faktorbasis gewählt. Dadurch existieren zu einem $a$ mehr Werte für $b$ als beim MPQS. Dies reduziert die Rechenzeit beim Wechsel des Polynoms. Dieses Verfahren wurde von René Peralta sowie William Robert Alford und Carl Pomerance 1995 entdeckt.

Vorfaktoren

Man kann das ganze Verfahren anstatt auf die Zahl $n$ auch auf ein Vielfaches $kn$ anwenden. Durch das Ändern der zu faktorisierenden Zahl ändert sich in der Regel auch die Faktorbasis. Durch die geschickte Wahl des Vorfaktors kann man zusätzliche Faktoren in die Faktorbasis integrieren. Für die Länge der zu untersuchenden Zahlen ohne den Faktor aus der Faktorbasis, der durch Sieben aus den Zahlen herausgestrichen wird, gilt: Ein kleiner Faktor in der Faktorbasis reduziert die Länge der Zahlen mehr als ein großer Faktor. Durch die Variation von $k$ kann man die Anzahl von kleinen Faktoren in der Faktorbasis erhöhen und so die Wahrscheinlichkeit, eine glatte Zahl zu erhalten, steigern. Durch die Multiplikation mit $k$ wachsen die erzeugten Zahlen aber an. Mit der sogenannten Knuth-Schroeppel Funktion werden beide Effekte berücksichtigt. Ein guter Vorfaktor kann dadurch effizient bestimmt werden. Die Integration des Faktors 2 in die Faktorbasis hat gewisse zusätzliche Vorteile. Um diesen Faktor aus den Kandidaten für glatte Zahlen herauszudividieren, müssen lediglich Shifts statt komplexer Divisionen ausgeführt werden. Wenn für $kn$ folgendes gilt

$k\cdot n=1\mod 8$

dann gilt für alle erzeugten Zahlen

$q(x)=(2x+b)^{2}-n=0\mod 8$

das heißt, man untersucht nur ungerade Zahlen und alle erzeugten Zahlen beinhalten einen Faktor 8. Als mehrfaches Polynom mit $a=1$ würde man einen Faktor 4 erwarten. Die so erzeugten Zahlen enthalten also einen zusätzlichen Faktor 2.

Implementierungen

• msieve, eine Implementierung des Multiple Polynomial Quadratic Sieve mit Unterstützung von partiellen Relationen. Geschrieben von Jason Papadopoulos.
• YAFU, von Ben Buhrow, ist wohl die schnellste Implementierung des Self Initializing Quadratic Sieve.
• Faktorisierungs Applet von Dario Alpern. Eine JavaScript-Implementierung des SIQS.
• Die open source java-math-library von Tilman Neumann enthält PSIQS, vermutlich das schnellste in Java geschriebene Quadratische Sieb.

Literatur

• Carl Pomerance: A Tale of Two Sieves. Notices of the AMS, 43 (1996) S. 1473–1485. (Webversion: http://www.ams.org/notices/199612/pomerance.pdf)
• Richard Crandall, Carl Pomerance: Prime Numbers, A Computational Perspective. Springer, 2001, ISBN 0-387-94777-9.
• Arjen K. Lenstra, Mark S. Manasse: Factoring With Two Large Primes. EUROCRYPT 1990, S. 72–82.
• James A. Davis, Diane B. Holdridge: Factorization Using the Quadratic Sieve Algorithm. CRYPTO 1983, S. 103–113.
• Joseph Gerver: Factoring Large Numbers with a Quadratic Sieve. Math. Comp. 41 (1983), Nr. 163, S. 287–294.

Weblinks

• schule.de (PDF; 257 kB) – sehr gute Einführung (deutsch)
• https://pdfs.semanticscholar.org/ (PDF) – Detaillierte Beschreibung des (Self Initializing) Quadratic Sieves von Scott Patrick Contini (englisch).
• http://www.karlin.mff.cuni.cz/ (PDF; 392 kB) – Beschreibung des (Self Initializing) Quadratic Sieves von Marian Kechlibar (englisch). (PDF; 392 kB)
• alpertron.com.ar – Java-Applet zur Faktorisierung von Zahlen (verwendet auch das Self Initializing Quadratic Sieve)
• The Quadratic Sieve Factoring Algorithm. (Memento vom 3. Dezember 2008 im Internet Archive) (PDF; 123 kB) Überblick über das Quadratische Sieb von Eric Landquist (englisch).
• math.colostate.edu (PDF; 50 kB) Demonstration des Quadratische Siebs am Beispiel der Zahl 87463 (englisch).
• cdc.informatik.tu-darmstadt.de – Der Block Lanczos Algorithmus über GF(2) von Olaf Gross.