Zahlkörpersieb

Zahlkörpersieb

Das Zahlkörpersieb (Number Field Sieve) 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.

Inhaltsverzeichnis

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 bmr 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.

1992 gelang mit Hilfe des speziellen Zahlkörpersiebs die Faktorisierung von F9.

Bereits 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[1].

Asymptotische Laufzeit

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

e^{(C+o(1))(n)^\frac13(\log n)^\frac23}

berechnen. n bezeichnet hierbei die Bitlänge der Zahl. Dabei ist die Konstante C 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. Meldung der Faktorisierung von RSA-200

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Gittersieb — Das Zahlkörpersieb (Number Field Sieve) 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… …   Deutsch Wikipedia

  • Faktorisierungsproblem — Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie. Dabei soll zu einer zusammengesetzten Zahl ein nichttrivialer Teiler ermittelt werden. Ist beispielsweise die Zahl 91… …   Deutsch Wikipedia

  • Faktorisierungsproblem für ganze Zahlen — Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie. Dabei soll zu einer zusammengesetzten Zahl ein nichttrivialer Teiler ermittelt werden. Ist beispielsweise die Zahl 91… …   Deutsch Wikipedia

  • Geschichte der Faktorisierungsverfahren — Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie. Dabei soll zu einer zusammengesetzten Zahl ein nichttrivialer Teiler ermittelt werden. Ist beispielsweise die Zahl 91… …   Deutsch Wikipedia

  • Faktorisierungsverfahren — Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie. Dabei soll zu einer zusammengesetzten Zahl ein nichttrivialer Teiler ermittelt werden. Ist beispielsweise die Zahl 91… …   Deutsch Wikipedia

  • Quadratisches Sieb — ist ein Begriff aus dem Bereich Zahlentheorie der Mathematik und bezeichnet einen der schnellsten bekannten Algorithmen zur Faktorisierung großer natürlicher Zahlen. Es ist ein allgemeines Faktorisierungsverfahren, d.h. die Laufzeit hängt nur von …   Deutsch Wikipedia

  • Daniel J. Bernstein — Daniel Bernstein (2010) Daniel Julius Bernstein (* 29. Oktober 1971 in East Patchogue, Long Island, New York) ist deutsch amerikanischer Mathematiker (Algorithmische Zahlentheorie), Kryptologe, Programmierer und Professor an der …   Deutsch Wikipedia

  • Jens Franke — (* 29. Juni 1964) ist ein deutscher Mathematiker. Leben Franke studierte von 1983 bis 1986 in Jena Mathematik und promovierte dort 1986 über elliptische Randwertprobleme in Besov Triebel Lizorkin Räumen bei Hans Triebel. Von 1986 bis 1988 war er… …   Deutsch Wikipedia

  • Nfs — Die Abkürzung NFS steht für: Nachrichten für Seefahrer, amtliche Veröffentlichung für die Seeschifffahrt Need for Speed, eine Computerspiel Serie Network File System, ein Netzwerkprotokoll. Neue Frankfurter Schule, eine Gruppe von Satirikern und… …   Deutsch Wikipedia

  • Pollard-Rho-Methode — Grafische Darstellung der Teilergebnisse Die Pollard Rho Methoden sind Algorithmen zur Bestimmung der Periodenlänge einer Zahlenfolge, die mit einer mathematischen Funktion berechnet wird. Verschiedene schwierige mathematische Probleme wie der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”