Zahlkörpersieb - LinkFang.de





Zahlkörpersieb


Das Zahlkörpersieb (englisch number field sieve, NFS) ist ein Begriff aus dem mathematischen Teilgebiet der Zahlentheorie. Es ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer Zahlen.

Das Zahlkörpersieb wird vor allem für Zahlen mit über 100 Stellen benutzt, die durch andere Verfahren nicht zerlegt werden konnten. Typischerweise werden dabei mehrere 100 Rechner parallel betrieben.

Entstehungsgeschichte

1988 schrieb John M. Pollard einen Brief an Andrew Odlyzko mit Kopien an Richard P. Brent, John Brillhart, Hendrik Lenstra, Claus-Peter Schnorr und Hiromi Suyama, worin er ein neues Faktorisierungsverfahren für ganz spezielle Zahlen beschrieb. In diesem Brief illustrierte er dieses Verfahren an der Fermat-Zahl F7 und vermutete, dass damit die bis dato noch nicht faktorisierte Zahl F9 möglicherweise ein Kandidat für dieses Verfahren ist. Pollard benutzte aber noch kein Siebverfahren im algebraischen Zahlkörper.

In den Folgejahren wurde diese Idee unter anderem von Arjen Lenstra, H. W. Lenstra, Mark Manasse und John M. Pollard ausgebaut. Daraus entstand das spezielle Zahlkörpersieb (wie das Verfahren heutzutage bezeichnet wird, um es vom allgemeinen Zahlkörpersieb unterscheiden zu können). Das spezielle Zahlkörpersieb lässt sich nur für Zahlen der Form [math]b^m-r[/math] mit b, r klein und m groß anwenden.

Das allgemeine Zahlkörpersieb wurde annähernd zur gleichen Zeit zum speziellen Zahlkörpersieb von Joe Buhler, H. W. Lenstra und Carl Pomerance gefunden. Dieses ist für beliebige Zahlen anwendbar, dafür muss man aber Einbußen bei der Geschwindigkeit hinnehmen.

1990 gelang mit Hilfe des speziellen Zahlkörpersiebs die Faktorisierung von F9[1].

1991 publizierte Pollard eine Variante des Zahlkörpersiebs, bei der ein zweidimensionales Sieb benutzt wird, welches er als Gittersieb bezeichnet. Mit dieser Gittersiebvariante, kombiniert mit anderen Methoden, wurde von 2003 bis 2005 eine 200-stellige Dezimalzahl (genannt RSA-200) faktorisiert.[2]

Asymptotische Laufzeit

Die asymptotische Laufzeit des Zahlkörpersiebs konnte bislang nicht exakt bewiesen werden. Unter einigen als wahrscheinlich geltenden Annahmen kann man diese jedoch für eine Zahl n zu

[math]e^{(C+o(1))(\log n)^\frac13(\log \log n)^\frac23}[/math]

berechnen. Damit ist die Laufzeit subexponentiell, aber immer noch superpolynomial, in der Länge der Zahl n. Die Konstante C ist davon abhängig, ob das spezielle oder das allgemeine Zahlkörpersieb benutzt wird:

  • Spezielles Zahlkörpersieb: C=(32/9)1/3
  • Allgemeines Zahlkörpersieb: C=(64/9)1/3

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 )
  • A. K. Lenstra, H. W. Lenstra, Jr.: The development of the number field sieve, Lecture Notes in Mathematics, V. 1554, 1993

Weblinks

Einzelnachweise

  1. Fermat factoring status. Abgerufen am 1. November 2015.
  2. Meldung der Faktorisierung von RSA-200 .

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Zahlkörpersieb (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.