Quadratisches Sieb

Stichpunkte

Allgemein
	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 showTocToggle("Anzeigen"
	"Verbergen") 1 Entstehungsgeschichte 2 Funktionsweise 2.1 Siebschritt 2.2 Auswahlschritt 2.3 Beispiel 3 Einsatzbereich 4 Literatur 5 Weblinks [Bearbeiten]
Entstehungsgeschichte
	Aufbauend auf der Kettenbruchmethode von John Brillhart und Michael Morrison
	welches schneller war
	als alle bis dahin bekannten Faktorisierungsverfahren
	sowie inspiriert durch das lineare Sieb von Richard Schroeppel erfand Carl Pomerance 1981 durch theoretische Ãœberlegungen das Quadratische Sieb
	Kurz darauf fanden Jim Davis und Diane Holdridge bzw
	Peter Montgomery unabhängig voneinander eine Variante des Quadratischen Siebs mit mehrfachen Polynomen (genannt MPQS)
	stammt von M
	das so genannte spezielle quadratische Sieb
	Eine andere Verbesserung
	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. [Bearbeiten]
Funktionsweise
	Die Idee des Quadratischen Siebs besteht darin
	eine Kongruenzen der Form <math>x^2equiv y^2 pmod{n}<math> zu finden
	Denn daraus folgt <math>x^2-y^2equiv 0 pmod{n} Rightarrow (x+y)(x-y)equiv 0 pmod{n}<math> Und falls n kein Teiler von (x+y) oder (x-y) ist
	(x+y) oder (x-y) teilen
	so muss ein Teiler von n
	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
	den Siebschritt
	bei dem Kongruenzen gesucht werden und dem Auswahlschritt
	Der Algorithmus lässt sich dabei in zwei Schritte aufteilen
	mit denen sich die gesuchte Zerlegung finden lässt. [Bearbeiten]
	bei dem aus diesen Kongruenzen geeignete ausgewählt werden
Siebschritt
	Im Siebschritt werden Kongruenzen der Form x2 â‰¡ 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)
	reduziert deren Quadrat modulo n und berechnet für diese (vergleichsweise kleinen) Zahlen die Primfaktorzerlegung mittels (unvollständiger) Probedivision aus
	Hierfür wählt man für x Zahlen knapp über der Wurzel von n aus
	so hat man eine der gesuchten Kongruenzen gefunden
	Besteht die Primfaktorzerlegung nur aus kleinen Primzahlen
	und führt die Probedivision nur bei diesen Zahlen durch. Im Detail geht man dabei wie folgt vor: Schritt 1: Wahl einer Faktorbasis
	die nur kleine Primfaktoren besitzen
	ähnlich dem Sieb des Eratosthenes Zahlen
	Aus Geschwindigkeitsgründen ermittelt man zuerst mit Hilfe eines Siebverfahrens
	bis zu einer Schranke S
	Dies sind die Primzahlen
	die quadratischer Rest modulo n sind
	Bei einer Variante
	die die Zahlen x symmetrisch um die Wurzel aus n verteilt benötigt man zusätzlich noch die Zahl -1
	die quadratische Nichtreste enhalten
	da solche Zahlen niemals zu einer gewünschten Kongruenz führen
	Die Schranke S wählt man in der Größenordnung von <math>S:=expleft(frac{1}{2}(ln n)^{frac{1}{2}}(ln ln n)^{frac{1}{2}}right)<math> Zahlen
	können à priori ausgeschlossen werden
	Schritt 2: Siebschritt
	Zuerst fertigt man eine Liste mit den Werten Q(x):=x2-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
	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
	Die Zahlen
	sondern deren auf ganze Zahlen gerundete Logarithmen
	Zum einen speichert man nicht die Zahlen Q(x) selbst
	Im Siebschritt kann man dann die Division durch eine Subtraktion mit den ebenfalls gerundeten Logarithmen der Zahlen p ersetzen
	sowie kleine Primzahlen weg
	Weiterhin lässt man im Siebprozess die Potenzen
	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 nach dem Sieben (in der Variante mit Logarithmen) kleiner als T sind
	Die Zahlen aus der Liste
	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. [Bearbeiten]
Auswahlschritt
	Hat man im Siebschritt genügend Kongruenzen gefunden
	so kann man aus diesen ein lineares Gleichungssystem über dem endlichen Körper F2 aufstellen
	Nun sucht man eine nichttriviale Linearkombination von Zeilen
	die den Nullvektor ergeben
	so ergibt sich gerade eine Kongruenz der Form u2 â‰¡ v2 (mod n) ergeben
	Multipliziert man die so gefundenen Kongruenzen miteinander
	der in mindestens der Hälfte aller Fälle weder 1 noch n ist
	Diese liefert durch Berechnung von ggT(u-v
	n) einen Faktor von n
	wie das Gaußsches_Eliminationsverfahren
	Zur Lösung dieses Schrittes verwendet man Verfahren der Linearen Algebra
	das Verfahren der Konjugierte Gradienten oder das Lanczos Verfahren. [Bearbeiten]
Beispiel
	Gesucht ist die Primfaktorzerlegung von 1909
	6921
	Die Quadratwurzel aus 1909 ist ungefähr 43
	also die 44 sein
	Die erste zu prüfende Zahl muß also die nächst höhere natürliche Zahl nach der 43
	so erhält man: (44·47)2 â‰¡ 3·3·3·2·2·3·5·5 â‰¡ 902 (mod 1909) und mit ggT(44·47-90
	d.h. multipliziert man jeweils die linke und rechte Seite der Kongruenz
	1909) = 23 einen Teiler von 1909 und damit die Zerlegung 1909=23·83
	Im Siebschritt berechnet man der Reihe nach: 442 ≡ 3·3·3 (mod 1909) 452 ≡ 2·2·29 (mod 1909) 462 ≡ 3·3·23 (mod 1909) 472 ≡ 2·2·3·5·5 (mod 1909) Fasst man die erste und die vierte Kongruenz zusammen
	Da sowohl 23 als auch 83 Primzahlen sind
	ist gleichzeitig auch schon die Primfaktorzerlegung gefunden. [Bearbeiten]
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. [Bearbeiten]
Literatur
	Carl Pomerance: Prime Numbers
	43 (1996) 1473-1485 (Webversion: http://www.ams.org/notices/199612/pomerance.pdf ) Richard Crandall
	Carl Pomerance: A Tale of Two Sieves
	ISBN 0-387-94777-9 [Bearbeiten]
	A Computational Perspective
	Springer
	2001
	Notices of the AMS
Weblinks
	http://www.thorstenreinecke.de/qsieve/ - Eine Implementierung des Quadratischen Siebs unter GPL en:Quadratic sieve fr:Crible quadratique

Dieser Artikel basiert auf dem Artikel Quadratisches Sieb aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.