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. 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 {\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

Gesucht ist eine Zerlegung einer natürlichen Zahl $n$ in Faktoren. Die Idee des Quadratischen Siebs besteht darin, Zahlen $x$ und $y$ zu finden, so dass die Kongruenz $x^{2}\equiv y^{2}{\pmod {n}}$ gültig ist.

Denn daraus folgt $x^{2}-y^{2}\equiv 0{\pmod {n}}\Rightarrow (x+y)(x-y)\equiv 0{\pmod {n}}$

Falls 1 < ggT ($x+y$,n) < n und damit auch 1 < ggT( $x-y$, n) < n, liefern der ggT($x+y,n$) und der ggT($x-y,n$) zwei der gesuchten Faktoren.

Bei der Faktorisierungsmethode von Fermat versucht man eine solche quadratische Kongruenz durch Durchlaufen der Werte von x zu erzeugen. Beim Quadratischen Sieb betrachtet man mehrere Kongruenzen der Form x^2 = k (mod n) und versucht dann, möglichst effizient aus diesen eine quadratische Kongruenz zu erzeugen.

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

$41^{2}-1649=32=2^{5}$

$42^{2}-1649=115=5*23$

$43^{2}-1649=200=2^{3}*5^{2}$

Keine dieser Zahlen ist ein Quadrat. Das Produkt der der ersten und der letzten Zeile 32 * 200 = 6400 = 2⁵ * 2³ * 5² = 2⁸ * 5² jedoch ist ein Quadrat, da die Exponenten der Primfaktordarstellung gerade sind. Damit haben wir die folgende quadratische Kongruenz gefunden:

$(41\cdot 43)^{2}\equiv 80^{2}\mod {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.

Der Algorithmus lässt sich in zwei Schritte aufteilen:

1. Der Siebschritt, bei dem Kongruenzen der Form x^2 = k (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² ≡ k (mod n)

gesucht, wobei die Primfaktorzerlegung von k bekannt ist und nur aus kleinen Primzahlen besteht (in anderen Worten: k soll bezüglich einer festen Schranke glatt sein). Man wählt die Zahlen x in der Nähe der Wurzel von n, damit so 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 die Lösungen der Quadratischen Gleichung Q(x)=x^2-n gefunden hat kann man eine ganze Sequenz von Q(x) bestimmen, die durch p teilbar sind. Das Bestimmen einer Quadratischen Wurzel 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 leiten seinen Namen vom Lösen der 'Quadratischen' Gleichung und dem 'Sieben' der Teiler ab.

Im Detail geht man dabei 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) ist lösbar. Zahlen, die quadratische Nichtreste enthalten, können a priori ausgeschlossen werden, da solche Zahlen niemals zu einer gewünschten Kongruenz führen. Die Schranke S wählt man in der Größenordnung von $S:=\exp \left({\frac {1}{2}}{\sqrt {\log n\log \log n}}\right)$ Schritt 2: Siebschritt. Wahl eins 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(x)=x2-n mod p für alle Faktoren p der Faktorbasis (sowie deren Exponenten). Teile alle Zahlen Q (x+k*p) innerhalb eines gewählten Siebintervalls durch p. Die Zahlen, bei denen am Ende eine 1 übrig bleibt, sind glatt bezüglich der Faktorbasis und damit die gesuchten Werte. Divisionen bei großen Zahlen Q(x) sind sehr langsam, daher modifiziert man diesen Schritt. Man speichert nicht die Zahlen Q(x) selbst, sondern deren auf ganze Zahlen gerundete Logarithmen, die viel kleiner sind. Im Siebschritt kann man dann die Division durch eine Subtraktion mit den ebenfalls gerundeten Logarithmen der Zahlen p ersetzen. Aus Geschwindigkeitsgründen verzichtet man in der Praxis auch auf das Sieben mit Potenzen der Faktoren. Durch diese Modifikationen sind nicht alle gefundenen Zahlen notwendiger Weise glatt. Schritt 3: Bestimmung der Primfaktorzerlegung der glatten Zahlen. Bestimme eine Schranke T. Die Zahlen aus der Liste, die nach dem Sieben (in der Variante mit Logarithmen) kleiner als T sind, sind mit hoher Wahrscheinlichkeit glatt. Für diese Zahlen berechnet man nun die Primfaktorzerlegung; dabei bemerkt man auch Zahlen, die doch nicht glatt sind. Das Bestimmen der Primfaktorzerlegung könnte kann man (wieder) mit der Probedivision erledigen. Schneller geht es wenn man Schritt 2 (modifiziert) noch einmal anwendet. Man bestimmt mit dem Sieb wieder alle Positionen x+kp die durch p teilbar sind. Nur die Zahlen Q(x+kp) die mit hoher Wahrscheinlichkeit glatt sind werden durch p geteilt.

Auswahlschritt

Hat man im Siebschritt genügend Kongruenzen gefunden, wird von diesen eine Teilmenge bestimmt, die eine Kongruenz der Form

$u^{2}\equiv v^{2}{\pmod {n}}$.

ergibt. Es wird also eine Teilmenge von Kongruenzen gesucht, die miteinander multipliziert, auch auf der rechten Seite ein Quadrat ergeben. Zu einer (glatten) Kongruenz x^2 = k (mod n) besteht k nur aus Faktoren der Faktorbasis. k kann vollständig als Vektor der Exponenten seiner bekannten Primzahlzerlegung beschreiben 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 seiner Primzahlzerlegung gerade sind. Falls man also eine nichttriviale Linearkombination von Zeilen findet, die den Nullvektor ergeben, hat man auch ein 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 Schrittes 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ße - aber sehr dünn besetzte Matrizen - in einem Bruchteil des Siebschritts Platz sparend (linear in der Anzahl der Zeilen) lösen .

Beispiel

Gesucht ist die Primfaktorzerlegung von n=87463. Sei S=30 Die Faktorbasis besteht dann aus den Primzahlen 2,3,13,17,19,29 da für p = 5,7,11 und 23 x^2 - n mod p keine Lösung hat (und damit nie ein Teiler von x^2 - n sein kann). Die Lösungen von x^2 - n mod p sind:

p	2	3	13	17	19	29
x	1	1,2	5,8	7,10	5,14	12,17

$\lfloor {\sqrt {n}}\rfloor =295$ Wir wählen L = 30. Durch Sieben erhält man folgende glatten Zahlen mit ihrer Primfaktorzerlegung. Die Matrix der Exponenten der Primfaktorzerlegung mod 2 sieht wie folgt aus:

x	Q(x) = x^2-n	-1	2	3	13	17	19	29
265	-1 * 2 · 3 · 132 · 17	1	1	1	0	1	0	0
278	-1 * 33 · 13 · 29	1	0	1	1	0	0	1
296	32 · 17	0	0	0	0	1	0	0
299	2 · 3 · 17 · 19	0	1	1	0	1	1	0
307	2 · 32 · 13 · 29	0	1	0	1	0	0	1
316	36 · 17	0	0	0	0	1	0	0

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.

Partielle Relationen

Selbst Relationen die nicht glatt sind, können zu 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}}$

bei der alle Faktoren mit ungeraden Exponenten aus der Faktorbasis stammen.

Das Bestimmen des Faktors P kostet dabei nur einen geringen Mehraufwand, da der Faktor P nach dem Sieben (mit Faktoren der Faktorbasis) übrig bleibt. Durch partielle Relationen kann man die für den Auswahlschritt brauchbaren Relationen erhöhen. Die Laufzeit kann damit halbiert werden.

Mehrfache Polynome

Das Multiple Polynomial Quadratic Sieve beruht auf der Idee nur Werte Q(x) zu erzeugen, die einen Faktor a als Teiler enthalten. Dazu betrachtet man anstelle der Gleichungen Q(x) = x^2 - n nun

$Q_{a,b}(x)=(ax+b)^{2}-n=a^{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,b}(x)=(ax+b)^{2}-N=a*(a+2bx+c)$

und der hiermit erzeugte Wert Q(x) enthält a als Teiler. Beim Multiple Polynomial Quadratic Sieve (MPQS) wählt man a = d^2. Damit enthält Q(x) ein Quadrat und die Wahrscheinlichkeit dass die erzeugten Zahlen Q(x) glatt sind steigt. Das Verfahren wurde 1983 von J.A.Davis und D.B.Holdridge entwickelt.

Beim Self Initializing Quadratic Sieve (SIQS) wird a als Produkt von Faktoren der Faktorbasis gewählt. Auch hier steigt die Wahrscheinlichkeit dass Q(x) glatt ist. Im Gegensatz zum MPQS existieren zu einem a viele Werte für b. Da sich das Wechseln des Faktors a der Polynome (im Gegensatz zum Wechseln von b) ungünstig auf die Laufzeit auswirkt, 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 email (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.crypto-world.com/documents/siqs.ps.gz - Detailierte Beschreibung des (Self Initializing) Quadratic Sieves von Scott Patrick Contini (englisch).
• 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