Quadratisches Sieb

Quadratisches Sieb ist ein Begriff aus dem Bereich Zahlentheorie der Mathematik.

Das Quadratische Sieb ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer Zahlen.

Inhaltsverzeichnis

1 Entstehungsgeschichte

2 Funktionsweise

2.1 Siebschritt
2.2 Auswahlschritt
2.3 Beispiel

3 Einsatzbereich

4 Literatur

5 Weblinks

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 Jim 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 berühmte 129-stellige Zahl RSA-129 zu faktorisieren.

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

Funktionsweise

Die Idee des Quadratischen Siebs besteht darin, eine Kongruenzen der Form $x^2\equiv y^2 \pmod{n}$ zu finden.

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

Und falls n kein Teiler von (x+y) oder (x-y) ist, so muss ein Teiler von n, (x+y) oder (x-y) teilen. Und genau diesen findet man mit ggT(x-y,n).

Mit dem Quadratischen Sieb versucht man nun möglichst effizient eine solche Kongruenz zu finden. Der Algorithmus lässt sich dabei in zwei Schritte aufteilen, den Siebschritt, bei dem Kongruenzen gesucht werden und dem Auswahlschritt, bei dem aus diesen Kongruenzen geeignete ausgewählt werden, mit denen sich die gesuchte Zerlegung finden lässt.

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). Hierfür wählt man für x Zahlen knapp über der Wurzel von n aus, reduziert deren Quadrat modulo n und berechnet für diese (vergleichsweise kleinen) Zahlen die Primfaktorzerlegung mittels (unvollständiger) Probedivision aus. Besteht die Primfaktorzerlegung nur aus kleinen Primzahlen, so hat man eine der gesuchten Kongruenzen gefunden.

Aus Geschwindigkeitsgründen ermittelt man zuerst mit Hilfe eines Siebverfahrens, ähnlich dem Sieb des Eratosthenes Zahlen, die nur kleine Primfaktoren besitzen, und führt die Probedivision nur bei diesen Zahlen durch.

Im Detail geht man dabei wie folgt vor:

Schritt 1: Wahl einer Faktorbasis. Dies sind die Primzahlen, die quadratischer Rest modulo n sind, bis zu einer Schranke S. Bei einer Variante, die die Zahlen x symmetrisch um die Wurzel aus n verteilt benötigt man zusätzlich noch die Zahl -1. Die Schranke S wählt man in der Größenordnung von

$S:=\exp\left(\frac{1}{2}(\ln n)^{\frac{1}{2}}(\ln \ln n)^{\frac{1}{2}}\right)$

Zahlen, die quadratische Nichtreste enhalten, können à priori ausgeschlossen werden, da solche Zahlen niemals zu einer gewünschten Kongruenz führen.

Schritt 2: Siebschritt. Zuerst fertigt man eine Liste mit den Werten Q(x):=x²-n für x wie oben beschrieben an. Danach geht man, analog zum Sieb des Eratosthenes für die Zahlen p aus der Faktorbasis (und theoretisch auch noch deren Potenzen) diese Liste durch und teilt diese Werte durch p. Die Zahlen, bei denen am Ende eine 1 übrig bleibt sind glatt bezüglich der Faktorbasis und damit die gesuchten Werte.

In der Praxis wird man aus Geschwindigkeitsgründen diesen Schritt etwas modifizieren. Zum einen speichert man nicht die Zahlen Q(x) selbst, sondern deren auf ganze Zahlen gerundete Logarithmen. Im Siebschritt kann man dann die Division durch eine Subtraktion mit den ebenfalls gerundeten Logarithmen der Zahlen p ersetzen. Weiterhin lässt man im Siebprozess die Potenzen, sowie kleine Primzahlen weg. Die gesuchten Werte können dann durch eine Abschätzung ermittelt werden (siehe Schritt 3).

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 mittels Probedivision die Primfaktorzerlegung; dabei bemerkt man auch Zahlen, die doch nicht glatt sind.

Auswahlschritt

Hat man im Siebschritt genügend Kongruenzen gefunden, so kann man aus diesen ein lineares Gleichungssystem über dem endlichen Körper F₂ aufstellen. Nun sucht man eine nichttriviale Linearkombination von Zeilen, die den Nullvektor ergeben. Multipliziert man die so gefundenen Kongruenzen miteinander, so ergibt sich gerade eine Kongruenz der Form

u² ≡ v² (mod n).

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ßsches_Eliminationsverfahren, das Verfahren der Konjugierte Gradienten oder das Lanczos Verfahren.

Beispiel

Gesucht ist die Primfaktorzerlegung von 1909. Die Quadratwurzel aus 1909 ist ungefähr 43,6921. Die erste zu prüfende Zahl muß also die nächst höhere natürliche Zahl nach der 43, also die 44 sein. Im Siebschritt berechnet man der Reihe nach:

44² ≡ 3·3·3 (mod 1909)
45² ≡ 2·2·29 (mod 1909)
46² ≡ 3·3·23 (mod 1909)
47² ≡ 2·2·3·5·5 (mod 1909)

Fasst man die erste und die vierte Kongruenz zusammen, d.h. multipliziert man jeweils die linke und rechte Seite der Kongruenz, so erhält man:

(44·47)² ≡ 3·3·3·2·2·3·5·5 ≡ 90² (mod 1909)

und mit ggT(44·47-90,1909) = 23 einen Teiler von 1909 und damit die Zerlegung 1909=23·83. Da sowohl 23 als auch 83 Primzahlen sind, ist gleichzeitig auch schon die Primfaktorzerlegung gefunden.

Einsatzbereich

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

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

Weblinks

http://www.thorstenreinecke.de/qsieve/ - Eine Implementierung des Quadratischen Siebs unter GPL