Stichpunkte

Allgemein
	Zahlkörpersieb ist ein Begriff aus dem Bereich Zahlentheorie der Mathematik. Das Zahlkörpersieb ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer Zahlen. Inhaltsverzeichnis showTocToggle("Anzeigen"
	"Verbergen") 1 Entstehungsgeschichte 2 Asymptotische Laufzeit 3 Einsatzbereich 4 Literatur [Bearbeiten]
Entstehungsgeschichte
	Am 31
	August 1988 schrieb J
	MP
	ollard einen Brief an AM
	Odlyzko mit Kopien an R
	PB
	rent
	JB
	rillhart
	HW
	Lenstra
	C.P
	Schnorr und H
	Suyama
	worin er ein neues Faktorisierungsverfahren für ganz spezielle Zahlen beschrieb
	dass damit die bis dato noch nicht faktorisierte Zahl F9 möglicherweise ein Kandidat für dieses Verfahren ist
	In diesem Brief illustrierte er dieses Verfahren an der Fermat-Zahl F7 und vermutete
	Pollard benutzte aber noch kein Siebverfahren im algebraischen Zahlkörper
	In den Folgejahren wurde diese Idee u.a. von A
	KL
	HW
	enstra
	M
	Lenstra
	SM
	anasse und JM
	Pollard ausgebaut
	Daraus entstand das spezielle Zahlkörpersieb (wie das Verfahren heutzutage bezeichnet wird
	um es vom allgemeinen Zahlkörpersieb unterscheiden zu können)
	r klein und m groß anwenden
	Das spezielle Zahlkörpersieb lässt sich nur für Zahlen der Form b^m-r mit b
	Das allgemeine Zahlkörpersieb wurde annähernd zeitgleich zum speziellen Zahlkörpersieb von J
	PB
	uhler
	HW
	Lenstra und Carl Pomerance erfunden
	dafür muss man aber Einbußen bei der Geschwindigkeit hinnehmen
	Dieses ist für beliebige Zahlen anwendbar
	1992 gelang mit Hilfe des speziellen Zahlkörpersiebs die Faktorisierung von F9
	Bereits 1991 publizierte J
	MP
	ollard eine Variante des Zahlkörpersiebs
	welches er als Gittersieb bezeichnetD
	bei der ein zweidimensionales Sieb benutzt wird
	iese Gittersiebvariante wurde 2003 benutzt um die bislang größte "allgemeine" zusammengesetzte Zahl zu faktorisieren: http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa576.html. [Bearbeiten]
Asymptotische Laufzeit
	Die asymptotische Laufzeit des Zahlkörpersiebs konnte bislang nicht exakt bewiesen werden
	kann man diese jedoch zu <math>e^{(C+o(1))(n)^frac13(log n)^frac23}<math> berechnen
	Unter einigen
	als wahrscheinlich geltenden Annahmen
	N bezeichnet hierbei die Länge der Zahl
	Dabei ist die Konstante C davon abhängig
	ob das spezielle oder das allgemeiner Zahlkörpersieb benutzt wird: Spezielles Zahlkörpersieb: C=(64/9)1/3=1.922999..
	Allgemeines Zahlkörpersieb: C=(32/9)1/3=1.526285... [Bearbeiten]
Einsatzbereich
	die durch andere Verfahren nicht zerlegt werden konnten
	Das Zahlkörpersieb wird vor allem für Zahlen mit über 100 Stellen benutzt
	Typischerweise werden dabei für den Siebschritt mehrere 100 Rechner parallel betrieben. [Bearbeiten]
Literatur
	Carl Pomerance: A Tale of Two Sieves
	43 (1996) 1473-1485 (Webversion: http://www.ams.org/notices/199612/pomerance.pdf ) A
	Notices of the AMS
	KL
	enstra & HW
	Lecture Notes in Mathematics
	Lenstra
	Jr.: The development of the number field sieve
	1554 Vorlage:Wikibooks1 en:General number field sieve fr:Algorithme de factorisation par crible sur les corps de nombres généralisé

Dieser Artikel basiert auf dem Artikel Zahlkörpersieb 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.