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. 110 Dezimalen-Stellen ist es das schnellste (allgemeine) Faktorisierungsverfahren. Für größere Zahlen ist das Zahlkörpersieb schneller. Es handelt sich um einen Las-Vegas-Algorithmus. Die Laufzeit zum Faktorisieren einer Zahl n ist (unter einigen als wahrscheinlich geltenden Annahmen) in der Größenordnung von

$\exp \left({\sqrt {\log n\log \log 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 so genannte spezielle quadratische Sieb, stammt von M. Zhang, welches aber nur auf spezielle Zahlen angewandt werden kann.

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

Wie die meisten modernen Faktorisierungsverfahren benutzt das Quadratische Sieb die Darstellung eines Produkts als Differenz von Quadraten. Sei $n=a*b$. Auf Grund der 3. Binomischen Formel gilt:

$\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {a-b}{2}}\right)^{2}={\frac {a^{2}+2ab+b^{2}}{4}}-{\frac {a^{2}-2ab+b^{2}}{4}}=ab=n$

Anstatt also die Teilbarkeit von Zahlen 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$:

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

Bei der Faktorisierungsmethode von Fermat durchläuft man die Werte von x, berechnet $q(x)=x^{2}-n$ und hofft dass q(x) ein Quadrat ist. Das Quadratische Sieb sammelt zu diversen x Werten die q(x) und versucht diese so zu 'multiplizieren' dass ein Quadrat entsteht.

Um solche Gleichungen multiplizieren zu können rechnen wir mit folgenden Kongruenzen:

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

Falls q ein Quadrat $y^{2}$ ist, und falls ggT ($x+y$,n) ungleich 1 ist, haben wir n zerlegt, denn es gilt dann: $x^{2}\equiv y^{2}{\pmod {n}}\Leftrightarrow x^{2}-y^{2}\equiv 0{\pmod {n}}\Rightarrow (x+y)(x-y)\equiv 0{\pmod {n}}$

Beispiel:

Sei die zu faktorisierede Zahl 1649. Schauen wir uns die Werte x² - n an, die bei der Faktorisierungsmethode von Fermat entstehen:

x	x2 - n	Primfaktorzerlegung
41	32	25
42	115	5 * 23
43	200	23 * 52
..
57	1600	402

Das erste Quadrat wird nach 16 Schritten mit x=57 gefunden. Das Produkt der Werte x² - n der ersten und der dritten Zeile jedoch ist auch ein Quadrat: 32 * 200 = 2⁵ * (2³ * 5²) = 2⁵⁺³ * 5²= 2⁸ * 5² (die Exponenten der Primfaktorzerlegung sind gerade).

Da 32 * 200 = 80² haben wir die folgende quadratische Kongruenz gefunden:

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

Da 41 * 43 mod 1649 = 114, lautet diese Kongruenz: 114² ≡ 80² (mod 1649). Mit ggT($114-80,1649$) = 17 (und ggT($114+80,1649$) = 97) haben wir 1649 = 17 * 97 in seine Faktoren zerlegt.

Im Allgemeinen sucht man in einer ersten Phase nach Kongruenzen. Hat man ausreichend viele gefunden, wird eine Teilmenge von Kongruenzen gesucht, die, miteinander multipliziert, auch auf der rechten Seite ein Quadrat ergeben. Falls man die Primfaktorzerlegung der Zahlen q kennt, wird die Multiplikation dieser Zahlen zur Addition der Exponenten ihrer Primfaktorzerlegung. Man betrachtet deswegen nur Zahlen q(x) deren Primfaktorzerlegung aus vorher festgelegten Faktoren bestehen. Damit besteht die Primfaktorzerlegung des Produkts auch nur aus diesen Faktoren. 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.

Betrachten wir dazu ein weiteres Beispiel. Gesucht ist die Primfaktorzerlegung von n=87463. Wir wollen nur Zahlen x² - n betrachten die aus kleinen Faktoren bestehen. Sei der größte Primfaktor 29. Da x² - n mod p für p = 5,7,11 und 23 keine Lösung hat kommen diese Zahlen niemals als Teiler von x² - 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 Nullvekor ergeben. Eine Lösung besteht aus Zeile 3 und Zeile 6.

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

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

ggT (x-y,n) = 587, ggT (x+y , n) = 149. Damit erhalten wir die Faktorisierung 87463 = 587 * 149.

Der Algorithmus lässt sich also in zwei Schritte aufteilen:

1. Der Siebschritt, bei dem Kongruenzen der Form x² = q (mod 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² ≡ 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²-n klein. Die Wahrscheinlichkeit, glatte Zahlen q(x) zu finden, ist damit hoch. Das Bestimmen der Primfaktorzerlegung durch Probedivision ist zeitintensiv. Um effizient zu überprüfen, ob eine Zahl glatt ist, benutzt man folgende Eigenschaft:

$q(x)=x^{2}-n$

$q(x+kp)=(x+kp)^{2}-n$

$q(x+kp)=x^{2}+2xkp+(kp)^{2}-n$

$q(x+kp)=q(x)+2xkp+(kp)^{2}$

$q(x+kp)\equiv q(x){\pmod {p}}$

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²-n genau dann, wenn x²=n mod p. Das Bestimmen der Quadratischen Wurzeln modulo einer Primzahl ist effizient (etwa mittels des Shanks-Tonelli Algorithmus) lösbar. Die Sequenz der ebenfalls durch p teilbaren Zahlen wird mit einen Siebverfahrens ä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.

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 x2 = n (mod p) lösbar ist. Zahlen, für die n quadratischer Nichtrest ist, können ausgeschlossen werden, da sie nicht als Teiler von x2-n auftreten. Je größer die Schranke gewählt wird, umso größer die Wahrscheinlichkeit, daß x2-n nur aus Primfaktoren bis zu dieser Schranke besteht. Der Nachteil ist, daß wir mehr Relationen brauchen 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:=\exp \left({\frac {1}{2}}{\sqrt {\log n\log \log n}}\right)$ Schritt 2: Siebe mit den Faktoren der Faktorbasis. Wähle ein Siebintervall in der Größenordnung von $L:=\exp \left({\sqrt {\log n\log \log n}}\right)$. Für die Zahlen x mit |x - √n| < L fertige eine Liste mit den Werten q(x):=x2-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*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 kann man etwa mit der Probedivision erledigen. Dabei muss man jedoch nur Divisionen von q(x) durch Zahlen p ausführen, die beim Sieben mit p getroffen wurden.

Auswahlschritt

Zu einer (glatten) Kongruenz x² = q (mod 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. Diese liefert durch Berechnung von 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 .

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^-2 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 für den Auswahlschritt brauchbaren Relationen erhöhen. Die Laufzeit kann damit halbiert werden.

Mehrfache Polynome

Wenn man zu einem gegebenen Siebintervall mehr glatte Zahlen Q(x) erzeugen könnte, würde der Algorithmus schneller terminieren. Das Multiple Polynomial Quadratic Sieve (MPQS) beruht auf der Idee nur Werte Q(x) zu erzeugen, deren Primfaktorzerlegung den Faktor a enthält. Wenn man a aus der Faktorbasis wählt steigt die Wahrscheinlichkeit dass Q(x) glatt ist. Das Multiple Polynomial Quadratic Sieve betrachtet anstelle der Gleichungen $Q(x)=x^{2}-n$ nun eine Menge von Polynomen

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

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

$Q_{a}(x)=(ax+b)^{2}-n=(ax)^{2}+2abx+b^{2}-n=a*(ax^{2}+2bx+c)$

und der hiermit erzeugte Wert $Q_{a}(x)$ enthält a als Faktor. Umso größer a gewählt wird desto glatter ist $Q_{a}(x)$, aber desto weniger Werte werden erzeugt.

Der Siebvorgang funktioniert ähnlich wie beim normalen Quadratischen Sieb, allerdings muss zu jedem Faktor p der Faktorbasis das multiplikative Inverse von a mod p berechnet werden. Da dieses Invertieren von a (etwa mit dem erweiterteren euklidischen Algorithmus) einen großen Anteil an der Gesamtrechenzeit verschlingt, gibt es für a einen optimalen Wert, der möglichst viele glatte Zahlen in einem gegebenen Zeitintervall liefert. Beim Multiple Polynomial Quadratic Sieve (MPQS) wählt man a als Quadrat. Das Verfahren wurde 1983 von J.A.Davis und D.B.Holdridge entwickelt.

Falls a aus der Faktorbasis ist, hat die Gleichung b^2 = n mod a für b wieder zwei Lösungen. 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. Es müssen weniger Polynome $Q_{a}(x)$ und damit weniger multiplikative Inverse berechnet werden, somit ist das SIQS schneller als das MPQS. Dieses Verfahren wurde von René Peralta sowie W.R.Alford und Carl Pomerance 1995 entdeckt.

Einsatzbereich

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

Am 2. April 1994 wurde die Zahl RSA-129 mit dem Multiple Polynomial Quadratic Sieve unter Ausnutzung partieller Relationen faktorisiert. Diese Zahl mit 129 Dezimal-Stellen wurde in ihre zwei Teiler (einer mit 64, der andere mit 65 Dezimal-Stellen) zerlegt. Der Siebschritt wurde verteilt von 600 Freiwilligen ausgeführt. Diese sammelten 8 Monate lange 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.

Literatur

• Carl Pomerance: A Tale of Two Sieves, Notices of the AMS, 43 (1996) 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: 72-82
• James A. Davis, Diane B. Holdridge: Factorization Using the Quadratic Sieve Algorithm. CRYPTO 1983: 103-113

Weblinks

• http://www.cdc.informatik.tu-darmstadt.de/reports/reports/denny.diplom.ps.gz - Diplomarbeit zum Multiple Polynomial Sieve von Thomas Friedrich Denny
• http://www.crypto-world.com/documents/siqs.ps.gz - Detaillierte Beschreibung des (Self Initializing) Quadratic Sieves von Scott Patrick Contini (englisch).
• http://www.karlin.mff.cuni.cz/~krypto/mpqs/main_file.pdf Beschreibung des (Self Initializing) Quadratic Sieves von Marian Kechlibar (englisch).
• http://www.alpertron.com.ar/ECM.HTM - Ein Java Applet zur Faktorisierung von Zahlen (verwendet auch das Self Initializing Quadratic Sieve)
• http://www.math.uiuc.edu/~landquis/quadsieve.pdf Überblick über das Quadratische Sieb von Eric Landquist (englisch).
• http://www.thorstenreinecke.de/qsieve/ - Eine Implementierung des Quadratischen Siebs unter GPL
• http://www.informatik.tu-darmstadt.de/KP/theses/Katja_Schmidt-Samoa.diplom.pdf - Grundlagen moderner Faktorisierungsverfahren und Laufzeitanalyse von Katja Schmidt-Samoa.
• http://www.math.colostate.edu/~hulpke/lectures/m400c/quadsievex.pdf Demonstration des Quadratische Siebs am Beispiel der Zahl 87463 (englisch).
• http://www.informatik.tu-darmstadt.de/ftp/pub/TI/reports/gross.diplom.ps.gz - Der Block Lanczos Algorithmus über GF(2) von Olaf Gross.
• http://www.boo.net/~jasonp/qs.html - Msieve von Jason Papadopoulos, eine schnelle und portierbare Implementierung des SIQS.