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

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:

Anstatt die Teilbarkeit einer Zahl zu untersuchen, sucht man eine Darstellung der Zahl als Differenz von Quadraten. Aus einer Darstellung erhält man die Teiler sowie von .

Bei der Faktorisierungsmethode von Fermat berechnet man den Wert für verschiedene Zahlen , bis man ein erhält, das eine Quadratzahl ist. Als erstes wählt man die kleinste Zahl, die größer als die Wurzel von ist. Anschließend zählt man in jedem Schritt um eins hoch. Wendet man dieses Verfahren beispielsweise zur Faktorisierung der Zahl 1649 an, so erhält man für die Werte in der folgenden Tabelle. Primfaktorzerlegung von 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 und des Quadrats die Faktorisierung von berechnen:

Wenn man die Funktionswerte zu und miteinander multipliziert, erhält man das Quadrat . 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 ein Vielfaches von ist:

Falls , aber weder noch teilt, dann gilt (für den größten gemeinsamer Teiler) und ist ein nichttrivialer Teiler von . Anstatt der Gleichung betrachtet man folgende Kongruenzen:

Diese Kongruenzen können nun multipliziert werden. Wenn man die Kongruenz zu

und

multipliziert, erhält man folgende Kongruenz

.

Man hat folgende quadratische Kongruenz gefunden: .

Mit und hat man 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 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 kennt, wird die Multiplikation dieser Zahlen zur Addition der Exponenten ihrer Primfaktorzerlegung. Man betrachtet deswegen nur glatte Zahlen , 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 . Man betrachtet nur Zahlen , die aus kleinen Faktoren bestehen. Sei der größte Primfaktor . Da für und keine Lösung hat, kommen diese Zahlen niemals als Teiler von vor. Die sogenannte Faktorbasis, in der alle möglichen Faktoren der Primfaktorzerlegung vorkommen, besteht also aus den Primzahlen . Die Matrix der Exponenten der Primfaktorzerlegung 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.

, . Damit erhält man die Faktorisierung .

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:

der Siebschritt, bei dem Kongruenzen der Form gesucht werden, und 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

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 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:

Wenn man also Stellen x gefunden hat, bei denen q(x) durch p teilbar ist, kann man eine ganze Sequenz von bestimmen, die durch p teilbar sind. p teilt genau dann, wenn . 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. alt=Die Bilder von 1 und 4 sind markiert, weil sie durch 5 teilbar sind. Deshalb sind auch die Bilder von 6=1+5, 9=4+5, 11=1+2*5 und 14=4+2*5 durch 5 teilbar.|mini|Für werden die Bilder der Elemente unter der Funktion auf Teilbarkeit durch 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 lösbar ist. Zahlen, für die n quadratischer Nichtrest ist, können ausgeschlossen werden, da sie nicht als Teiler von auftreten. Je größer die Schranke gewählt wird, umso größer die Wahrscheinlichkeit, dass 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

Schritt 2: Siebe mit den Faktoren der Faktorbasis.

Wähle ein Siebintervall in der Größenordnung von . Für die Zahlen x mit |x - √n| < L fertige eine Liste mit den Werten an. Bestimme die (zwei) Lösungen von für alle Faktoren p der Faktorbasis. Teile alle Zahlen 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 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 F2 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 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.Der Block Lanczos Algorithmus über GF(2) von Olaf Gross http://www.cdc.informatik.tu-darmstadt.de/reports/reports/gross.diplom.ps.gz

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.