Stichpunkte

Allgemein
	"Verbergen") 1 Entstehungsgeschichte 2 Funktionsweise 2.1 Siebschritt 2.2 Auswahlschritt 2.3 Beispiel 3 Einsatzbereich 4 Literatur 5 Weblinks [Bearbeiten]
	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"
Entstehungsgeschichte
	als alle bis dahin bekannten Faktorisierungsverfahren
	welches schneller war
	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
	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
	welches aber nur auf spezielle Zahlen angewandt werden kann
	Zhang
	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
	eine Kongruenzen der Form <math>x^2equiv y^2 pmod{n}<math> zu finden
	Die Idee des Quadratischen Siebs besteht darin
	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
	n)
	Und genau diesen findet man mit ggT(x-y
	Mit dem Quadratischen Sieb versucht man nun möglichst effizient eine solche Kongruenz zu finden
	bei dem Kongruenzen gesucht werden und dem Auswahlschritt
	bei dem aus diesen Kongruenzen geeignete ausgewählt werden
	Der Algorithmus lässt sich dabei in zwei Schritte aufteilen
	mit denen sich die gesuchte Zerlegung finden lässt. [Bearbeiten]
	den Siebschritt
Siebschritt
	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)
	Im Siebschritt werden Kongruenzen der Form x2 â‰¡ k (mod n) gesucht
	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
	so hat man eine der gesuchten Kongruenzen gefunden
	Besteht die Primfaktorzerlegung nur aus kleinen Primzahlen
	Aus Geschwindigkeitsgründen ermittelt man zuerst mit Hilfe eines Siebverfahrens
	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
	ähnlich dem Sieb des Eratosthenes Zahlen
	bis zu einer Schranke S
	die quadratischer Rest modulo n sind
	Dies sind die Primzahlen
	Bei einer Variante
	die die Zahlen x symmetrisch um die Wurzel aus n verteilt benötigt man zusätzlich noch die Zahl -1
	können à priori ausgeschlossen werden
	die quadratische Nichtreste enhalten
	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
	da solche Zahlen niemals zu einer gewünschten Kongruenz führen
	Schritt 2: Siebschritt
	Zuerst fertigt man eine Liste mit den Werten Q(x):=x2-n für x wie oben beschrieben an
	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
	Danach geht man
	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
	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
	sind mit hoher Wahrscheinlichkeit glatt
	Die Zahlen aus der Liste
	die nach dem Sieben (in der Variante mit Logarithmen) kleiner als T sind
	die doch nicht glatt sind. [Bearbeiten]
	Für diese Zahlen berechnet man nun mittels Probedivision die Primfaktorzerlegung; dabei bemerkt man auch Zahlen
Auswahlschritt
	Hat man im Siebschritt genügend Kongruenzen gefunden
	so kann man aus diesen ein lineares Gleichungssystem über dem endlichen Körper F2 aufstellen
	die den Nullvektor ergeben
	Nun sucht man eine nichttriviale Linearkombination von Zeilen
	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
	das Verfahren der Konjugierte Gradienten oder das Lanczos Verfahren. [Bearbeiten]
	Zur Lösung dieses Schrittes verwendet man Verfahren der Linearen Algebra
	wie das Gaußsches_Eliminationsverfahren
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
	d.h. multipliziert man jeweils die linke und rechte Seite der Kongruenz
	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
	so erhält man: (44·47)2 â‰¡ 3·3·3·2·2·3·5·5 â‰¡ 902 (mod 1909) und mit ggT(44·47-90
	1909) = 23 einen Teiler von 1909 und damit die Zerlegung 1909=23·83
	ist gleichzeitig auch schon die Primfaktorzerlegung gefunden. [Bearbeiten]
	Da sowohl 23 als auch 83 Primzahlen sind
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
	Notices of the AMS
	ISBN 0-387-94777-9 [Bearbeiten]
	43 (1996) 1473-1485 (Webversion: http://www.ams.org/notices/199612/pomerance.pdf ) Richard Crandall
	A Computational Perspective
	Carl Pomerance: Prime Numbers
	Carl Pomerance: A Tale of Two Sieves
	Springer
	2001
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.