Algorithmische Zahlentheorie

Die algorithmische Zahlentheorie ist ein Teilgebiet der Zahlentheorie, welche wiederum ein Teilgebiet der Mathematik ist. Sie beschäftigt sich mit der Frage nach effizienten algorithmischen Lösungen für zahlentheoretische Fragestellungen.

Wichtigste Bereiche der elementaren algorithmischen Zahlentheorie sind

Hierfür benötigt man weitere Verfahren, die ebenfalls untersucht werden:

Neue Forschungsergebnisse zur algorithmischen Zahlentheorie werden unter anderem auf der seit 1994 zweijährlich stattfindenden Konferenz ANTS (Algorithmic Number Theory Symposium) präsentiert.

Inhaltsverzeichnis

Anwendungen

Die wichtigste Anwendung der algorithmischen Zahlentheorie ist die Kryptographie. Hier wird beim RSA-Verfahren ausgenutzt, dass die Primzahleigenschaft einer Zahl schnell überprüft werden kann, aber bislang keine ähnlich schnellen Verfahren bekannt sind, eine zusammengesetzte Zahl (das ist eine Zahl, die nicht prim ist), zu faktorisieren.

Auf dieser Tatsache beruht insbesondere die Sicherheit der Datenübertragung im Internet. In diesem Zusammenhang hatte RSA Security größere Summen für diejenigen ausgelobt, denen es gelingt, bestimmte Zahlen zu faktorisieren. (Siehe http://www.rsasecurity.com/rsalabs/node.asp?id=2093)

Ein viel untersuchtes Problem mit weitreichenden Anwendungen ist es, in einem Zahlengitter eine das Gitter erzeugende Basis zu finden, die aus möglichst kurzen und möglichst orthogonalen Basisvektoren besteht (Gitterbasenreduktion).

Personen

Literatur

  • Willi Klösgen: Dokumentation über zahlentheoretische Probleme, die mit Hilfe elektronischer Datenverarbeitungsanlagen behandelt wurden. Mitteil. Ges. f. Math. u. Datenverarb. Nr. 3, Birlinghoven 1970
  • Garrett Birkhoff, Marshall Hall Jr.: Computers in Algebra and Number Theory. (SIAM-AMS Proceedings IV) AMS, Providence, 1971
  • Horst-Günter Zimmer: Computers and computations in algebraic number theory. In: S. R. Petrick (Hrsg.): SYMSAC '71, Proc. second ACM symposium on symbolic and algebraic manipulation, Los Angeles 1971, S. 172–179
  • H.-G. Zimmer: Computational Problems, Methods, and Results in Algebraic Number Theory. Lecture Notes Math. 262, Springer-Verlag 1972
  • Hendrik W. Lenstra, Robert Tijdeman (Hrsg.): Computational methods in number theory I, II. Math. Centre Tracts 154/155, Math. Centrum Amsterdam, 1982
  • Attila Pethö, Michael Pohst, Hugh Williams, Horst-Günter Zimmer (Hrsg.): Computational Number Theory. Proc. Coll. Debrecen 1989. Walter de Gruyter, 1991, ISBN 978-3110123944.
  • Michael Pohst, Hans Zassenhaus: Algorithmic Algebraic Number Theory. Cambridge University Press 1989, 1990, 1993, 1997, ISBN 0521596696.
  • Michael Pohst: Computational Algebraic Number Theory. DMV Seminar Bd. 21, Birkhäuser, Basel 1993, ISBN 3764329130.
  • Michel Waldschmidt, Pierre Moussa, Jean-Marie Luck, Claude Itzykson (Hrsg.): From number theory to physics. Winter school, Les Houches, 1989. Springer-Verlag 1992, 1995, ISBN 3540533427.
  • H. Krishna, B. Krishna, K.-Y. Lin, J.-D. Sun: Computational Number Theory and Digital Signal Processing. Fast Algorithms and Error Control Techniques. CRC Press 1994, ISBN 0-8493-7177-5.
  • Alf van der Poorten, Wieb Bosma (Hrsg.): Computational algebra and number theory (Sydney, 1992) (Mathematics and its applications 325) Kluwer, Dordrecht, 1995, ISBN 0-7923-3501-5, Paperback, Springer 2010, ISBN 978-9048145607.
  • Eric Bach, Jeffrey Shallit: Algorithmic Number Theory. Vol. I: Efficient Algorithms. MIT Press 1996, ISBN 0262024055.
  • Otto Forster: Algorithmische Zahlentheorie. Vieweg, 1996, ISBN 3-528-06580-X
    • Vgl. auch das zugehörige Programm ARIBAS
  • Duncan A. Buell, Jeremy T. Teitelbaum (Hrsg.): Computational Perspectives on Number Theory: Proc. Conf. in Honor of A.O.L. Atkin, Chicago 1995. (Ams/IP Studies in Advanced Mathematics 7) AMS 1997, ISBN 082180880X.
  • Kálmán Györy, Attila Pethö, Vera T. Sós (Hrsg.): Number Theory: Diophantine, Computational and Algebraic Aspects - Proc. Conf. Eger 1996. de Gruyter 1998, ISBN 978-3110153644.
  • Ramanujachary Kumanduri, Cristina Romero: Number theory with computer applications. Prentice Hall 1998, ISBN 013801812X.
  • Nigel Smart: The algorithmic resolution of diophantine equations. (London Mathematical Society Student Texts 41) Cambridge University Press, 1998, ISBN 052164156X.
  • Melvyn B. Nathanson (Hrsg.): Unusual applications of number theory: DIMACS Workshop, 2000. (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 64) AMS 2004, ISBN 978-0821827031.
  • Song Y. Yan: Number theory for computing. 2. Aufl., Springer-Verlag 2002, ISBN 3540430725.
  • Henri Cohen: A Course in Computational Algebraic Number Theory. 4. Auflage. Springer, Berlin 2003, ISBN 3-540-55640-0
  • Alf van der Poorten, Andreas Stein, Hugh C. Williams (Hrsg.): High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams. (Fields Institute Communications, Vol. 41) AMS 2004, ISBN 0821833537.
  • Richard E. Crandall, Carl Pomerance: Prime Numbers - A Computational Perspective. 2. Auflage. Springer, 2005 ISBN 0-387-25282-7
  • Victor Shoup: A computational introduction to number theory and algebra. Cambridge 2005, 2008, ISBN 0521851548. [7]
  • David Bressoud, Stan Wagon: A course in computational number theory. John Wiley 2008, ISBN 0470412151.

Einzelnachweise

  1. Nr. 129 von Mathematics of Computation, Band 29, wurde Lehmer im Januar 1975 anlässlich seines 70. Geburtstags gewidmet.
  2. Nr. 203 von Mathematics of Computation, Band 61, wurde im Juli 1993 dem Gedenken an Lehmer gewidmet.
  3. Anlässlich der Verabschiedung von Lenstra nach 17 Jahren an der Universität Berkeley fand im März 2003 eine wissenschaftliche Konferenz statt, das Lenstra Treurfeest – A Farewell Conference, March 21-23, 2003
  4. Heft 3 von Band 18 (2006) des Journal de Théorie des Nombres de Bordeaux wurde Pohst anlässlich seines 60. Geburtstags gewidmet. Journal de théorie des nombres de Bordeaux Volume 18, number 3 (2006)
  5. Nr. 177/178 von Mathematics of Computation, Band 48, wurde Shanks im Januar 1987 anlässlich seines 70. Geburtstags gewidmet.
  6. Zum 60. Geburtstag von Williams wurde 2003 in Banff (Canada) ihm zu Ehren eine wissenschaftliche Konferenz ausgerichtet (siehe Literatur). Fields Institute - Conference in Number Theory - 2003,Number Theory Conference in honour of Professor H. C. Williams | CISaC
  7. A Computational Introduction to Number Theory and Algebra. Shoup.net. Abgerufen am 19. September 2010.

Weblinks


Wikimedia Foundation.

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

  • Zahlentheorie — Die Zahlentheorie ist ein Teilgebiet der Mathematik, das sich im weitesten Sinn mit den Eigenschaften der Zahlen beschäftigt. Teilgebiete sind beispielsweise die elementare oder arithmetische Zahlentheorie – eine Verallgemeinerung der Arithmetik …   Deutsch Wikipedia

  • Algorithmische Komposition — Als Algorithmische Komposition (AK) bezeichnet man jene Kompositionsverfahren, bei denen die Partitur durch einen automatischen, mathematisch beschreibbaren Prozess oder Algorithmus erzeugt wird. Im Prinzip lässt sich jedes Musikstück als eine… …   Deutsch Wikipedia

  • Elementare Zahlentheorie — Ursprünglich ist die Zahlentheorie (auch: Arithmetik) ein Teilgebiet der Mathematik, das sich allgemein mit den Eigenschaften der ganzen Zahlen und insbesondere mit den Lösungen von Gleichungen in den ganzen Zahlen (Diophantische Gleichung)… …   Deutsch Wikipedia

  • Teilgebiet der Mathematik — Dieser Artikel ergänzt den Hauptartikel Mathematik und die Portalseite Mathematik. Er dient dazu, einen Überblick über die Teilgebiete der Mathematik zu geben (siehe auch Höhere Mathematik). Ein Charakteristikum der Mathematik ist der enge… …   Deutsch Wikipedia

  • Zweig der Mathematik — Dieser Artikel ergänzt den Hauptartikel Mathematik und die Portalseite Mathematik. Er dient dazu, einen Überblick über die Teilgebiete der Mathematik zu geben (siehe auch Höhere Mathematik). Ein Charakteristikum der Mathematik ist der enge… …   Deutsch Wikipedia

  • ARIBAS — ist ein Computerprogramm für zahlentheoretische Berechnungen. Es wurde von Otto Forster unter der GNU General Public License entwickelt. Inhaltsverzeichnis 1 Einordnung 2 Eine interaktive Beispielsitzung 3 Weitere Code Beispiele …   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

  • Otto Forster — im Mathematischen Forschungsinstitut Oberwolfach 1987 Otto Forster (* 8. Juli 1937 in München) ist ein deutscher Mathematiker. Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • Teilgebiete der Mathematik — Dieser Artikel ergänzt den Hauptartikel Mathematik und die Portalseite Mathematik. Er dient dazu, einen Überblick über die Teilgebiete der Mathematik zu geben (siehe auch Höhere Mathematik). Ein Charakteristikum der Mathematik ist der enge… …   Deutsch Wikipedia

  • Shafi Goldwasser — Shafrira „Shafi“ Goldwasser (* 1958 in New York City) ist eine US amerikanische Informatikerin. 1979 erlangte sie den Bachelor Grad in Mathematik an der Carnegie Mellon University, 1981 den Magister und 1983 den Doktortitel in Informatik an der… …   Deutsch Wikipedia

Share the article and excerpts

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