Quadratisches Sieb

Grundidee und Bedeutung

Das quadratische Sieb ist ein allgemeiner Algorithmus zur Faktorisierung großer natürlicher Zahlen. „Allgemein“ bedeutet, dass seine Laufzeit von der Größe der Zahl n abhängt, nicht von besonderen Eigenschaften ihrer Teiler. Für Zahlen mit bis zu etwa 100 Dezimalstellen gilt es als eines der schnellsten allgemeinen Verfahren; im Abschnitt zum Einsatzbereich wird seine praktische Eignung bis etwa 110 Dezimalstellen angegeben. Für größere Zahlen ist meist das Zahlkörpersieb schneller. Unter einigen als wahrscheinlich geltenden Annahmen liegt die Laufzeit in der Größenordnung

exp(√(ln n · ln ln n)).

Grundlage ist die dritte binomische Formel:

x² − y² = (x + y)(x − y) = n.

Statt Teiler direkt zu suchen, konstruiert man daher Quadrate, deren Differenz durch n teilbar ist. Findet man x² ≡ y² (mod n), kann ggT(x − y,n) oder ggT(x + y,n) einen nichttrivialen Faktor von n liefern. Das funktioniert, wenn n zwar das Produkt (x + y)(x − y), aber keinen der beiden Faktoren allein teilt. Nicht jede solche quadratische Kongruenz liefert eine Zerlegung; im Durchschnitt führt etwa jede zweite zu einer echten Faktorisierung.

Das Verfahren erweitert Fermats Methode. Diese berechnet q(x)=x²−n für aufeinanderfolgende x ab der kleinsten ganzen Zahl oberhalb von √n, bis q(x) selbst ein Quadrat ist. Beim quadratischen Sieb dürfen dagegen mehrere Kongruenzen x² ≡ q(x) (mod n) miteinander multipliziert werden. Dadurch genügt es, Funktionswerte zu finden, deren Produkt ein Quadrat ist.

Dazu verwendet man glatte Zahlen: Eine Zahl heißt bezüglich einer Faktorbasis glatt, wenn ihre Primfaktorzerlegung ausschließlich Primzahlen aus dieser vorher festgelegten Basis enthält. Ein Produkt ist genau dann ein Quadrat, wenn in seiner Primfaktorzerlegung alle Exponenten gerade sind. Das Finden geeigneter Relationen zerfällt deshalb in den Siebschritt und den anschließenden Auswahlschritt.

Siebschritt und Faktorbasis

Im Siebschritt sucht man Kongruenzen x² ≡ q (mod n), bei denen q vollständig in kleine bekannte Primfaktoren zerfällt. Man wählt x nahe bei √n, damit q(x)=x²−n klein bleibt und mit höherer Wahrscheinlichkeit glatt ist.

Die Faktorbasis enthält alle Primzahlen p bis zu einer Schranke S, für die n ein quadratischer Rest modulo p ist. Das heißt, x² ≡ n (mod p) besitzt eine Lösung. Ist n ein quadratischer Nichtrest, kann p kein Teiler von x²−n sein und wird ausgeschlossen. Als Größenordnung verwendet man

S := √(exp(√(ln n ln ln n))).

Eine größere Basis erhöht die Wahrscheinlichkeit glatter Werte, erfordert aber mehr Relationen für das spätere Gleichungssystem. Bei einer zu kleinen Basis zerfallen nur wenige Kandidaten vollständig.

Für jede Primzahl p der Basis werden die gewöhnlich zwei Lösungen von x² ≡ n (mod p) bestimmt, beispielsweise mit dem Shanks-Tonelli-Algorithmus. Ist q(x) durch p teilbar, dann gilt wegen q(x+kp) ≡ q(x) (mod p), dass auch alle entsprechenden Stellen im Abstand p durch p teilbar sind. Diese Stellen werden ähnlich wie beim Sieb des Eratosthenes markiert. Daher stammt der Name: Es wird eine quadratische Gleichung gelöst und anschließend nach Teilern gesiebt.

Das Siebintervall hat die Größenordnung

L := S² = exp(√(ln n ln ln n)),

wobei Werte mit |x−√n|<L untersucht werden. Im theoretischen Grundverfahren teilt man die betroffenen q-Werte durch p sowie durch p², p³ und weitere Potenzen. Bleibt 1 übrig, ist der Wert glatt.

In praktischen Implementierungen speichert man statt der großen q(x) ihre gerundeten Logarithmen. Eine Division durch p wird so zur Subtraktion von log p. Meist verzichtet man aus Geschwindigkeitsgründen auf das Sieben mit Primzahlpotenzen. Kandidaten, deren Restwert unter einer Fehlerschranke T liegt, gelten zunächst nur als wahrscheinlich glatt. Anschließend wird ihre tatsächliche Primfaktorzerlegung geprüft, etwa mit der Pollard-Rho-Methode für kleine Restfaktoren, durch ein zweites Sieben oder mithilfe eines ggT mit dem Produkt der Faktoren der Faktorbasis.

Auswahl durch lineare Algebra

Jede gefundene glatte Relation wird durch einen Exponentenvektor beschrieben: Seine Einträge sind die Exponenten der Primfaktoren aus der Faktorbasis, reduziert modulo 2. Aus diesen Vektoren entsteht ein lineares Gleichungssystem über dem endlichen Körper F₂. Eine nichttriviale Linearkombination von Zeilen, die den Nullvektor ergibt, bezeichnet eine Auswahl von Relationen, bei deren Produkt alle Exponenten gerade sind. Beide Seiten der daraus gebildeten Kongruenz sind somit Quadrate.

Aus u² ≡ v² (mod n) berechnet man ggT(u−v,n). In mindestens der Hälfte der Fälle ist das Ergebnis weder 1 noch n und damit ein echter Faktor. Zum Lösen des meist großen, aber sehr dünn besetzten Gleichungssystems dienen das gaußsche Eliminationsverfahren, das Verfahren der konjugierten Gradienten oder das Lanczos-Verfahren. Besonders das Block-Lanczos-Verfahren benötigt Speicherplatz nur linear zur Zahl der Zeilen und beansprucht gewöhnlich nur einen Bruchteil der Zeit des Siebschritts.

Ein Beispiel ist n=87463. Als Faktorbasis dienen 2, 3, 13, 17, 19 und 29; die Primzahlen 5, 7, 11 und 23 werden ausgeschlossen, weil x² ≡ n modulo diesen Zahlen keine Lösung besitzt. Unter den gefundenen Relationen sind q(296)=3²·17 und q(316)=3⁶·17. Ihre Exponentenvektoren ergeben zusammen modulo 2 den Nullvektor. Daraus folgen

x=296·316=93536 ≡ 6073 (mod n)

und

y=√(3²·17·3⁶·17)=3⁴·17=1377.

Es gilt ggT(x−y,n)=587 und ggT(x+y,n)=149, also 87463=587·149.

Typisches kleines Beispiel

Für n=1649 beginnt Fermats Methode mit x=41, weil dies die kleinste ganze Zahl oberhalb von √1649 ist. Sie findet erst bei x=57 den Wert q(57)=1600=40² und damit

1649=57²−40²=(57+40)(57−40)=97·17.

Das quadratische Sieb kann frühere Werte kombinieren: q(41)=2⁵ und q(43)=2³·5². Ihr Produkt ist 2⁸·5²=(2⁴·5)²=80². Aus

(41·43)² ≡ 80² (mod 1649)

folgen ggT(41·43−80,1649)=17 und ggT(41·43+80,1649)=97. Dieses Beispiel zeigt den entscheidenden Vorteil: Ein einzelner Funktionswert muss kein Quadrat sein; mehrere glatte Werte können gemeinsam eines bilden.

Verbesserungen des Verfahrens

Partielle Relationen erhöhen die Ausbeute des Siebens. Dabei darf eine Relation zusätzlich einen Faktor P außerhalb der Faktorbasis enthalten. Zwei partielle Relationen mit demselben P ergeben beim Multiplizieren den Faktor P². Dieser besitzt einen geraden Exponenten und stört den Auswahlschritt nicht; durch Multiplikation mit P⁻² erhält man sogar eine vollständig glatte Relation. Begrenzt man P, kann es mit geringem Mehraufwand erkannt werden. Partielle Relationen können die Laufzeit halbieren.

Beim Multiple Polynomial Quadratic Sieve (MPQS) wird das Suchintervall auf mehrere Polynome verteilt. Verwendet werden

qₐ(x)=(2ax+b)²−n,

wobei b²−n=4ac gilt. Deshalb ist

qₐ(x)=4a(ax²+bx+c)

und jeder erzeugte Wert enthält den bekannten Faktor 4a. Beim MPQS wählt man a als Quadrat einer Primzahl, sodass n ein quadratischer Rest modulo 4a ist. Die Kandidaten bleiben kleiner und sind daher häufiger glatt. Allerdings muss für jeden Faktor p der Faktorbasis das inverse Element von a modulo p berechnet werden. Beim Self Initializing Quadratic Sieve (SIQS) ist a ein Produkt von Faktoren der Faktorbasis; dadurch stehen mehr Werte für b zur Verfügung und der Wechsel zwischen Polynomen wird schneller.

Außerdem kann man statt n ein Vielfaches kn sieben. Ein geschickt gewählter Vorfaktor k verändert die Faktorbasis so, dass mehr kleine Primzahlen aufgenommen werden. Kleine Faktoren verkürzen die verbleibenden Kandidaten besonders stark, während die Multiplikation mit k die Ausgangswerte vergrößert. Die Knuth-Schroeppel-Funktion wägt beide Wirkungen ab. Gilt kn ≡ 1 (mod 8), enthalten die erzeugten Werte einen Faktor 8, was zusätzliche Vorteile beim schnellen Herausdividieren des Faktors 2 bietet.

Einsatz, Laufzeit und Entwicklung

Das quadratische Sieb eignet sich besonders für große Zahlen bis etwa 110 Dezimalstellen, sofern sie keine Primpotenzen sind. Bezeichnet N=log(n) die Eingabelänge, lässt sich seine Laufzeit schreiben als

e^(c·N^α·(log N)^(1−α)) mit α=1/2 und c=1.

Damit ist die Laufzeit superpolynomial, aber subexponentiell. Zum Vergleich: α=1 beschreibt exponentielles Wachstum; die Probedivision besitzt dieses Verhalten mit c=1/2. Bei α=0 wäre die Laufzeit polynomial. Beim Zahlkörpersieb ist α auf 1/3 reduziert, obwohl dort die asymptotisch weniger wichtige Konstante c wesentlich größer ist.

Carl Pomerance entwickelte das quadratische Sieb 1981 auf Grundlage der Kettenbruchmethode von John Brillhart und Michael Morrison und angeregt durch Richard Schroeppels lineares Sieb. James Davis und Diane Holdridge sowie unabhängig Peter Montgomery fanden kurz darauf die Variante mit mehreren Polynomen. Das MPQS-Verfahren von J. A. Davis und D. B. Holdridge stammt aus dem Jahr 1983; SIQS wurde 1995 von René Peralta sowie William Robert Alford und Carl Pomerance entdeckt.

1994 wurde RSA-129, eine Zahl mit 129 Dezimalstellen, mit MPQS und partiellen Relationen in Faktoren mit 64 beziehungsweise 65 Dezimalstellen zerlegt. 600 Freiwillige sammelten acht Monate lang Kongruenzen. Der Auswahlschritt verarbeitete 298 GB Daten in 45 Stunden auf einem Supercomputer. Die Faktorbasis umfasste 524338 Primzahlen, die Matrix 569466 Zeilen und 524338 Spalten. Spätere Faktorisierungsrekorde wurden mit dem Zahlkörpersieb erzielt.

Bekannte Implementierungen sind msieve für MPQS mit partiellen Relationen, YAFU für SIQS, das JavaScript-Faktorisierungs-Applet von Dario Alpern, PSIQS aus der java-math-library von Tilman Neumann sowie C Quadratic Sieve, eine 2022 veröffentlichte Public-Domain-Implementierung für Zahlen bis zu 330 Bit.