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 algorithmischen Zahlentheorie sind
*Tests zur Überprüfung der Primzahleigenschaft
• Verfahren' target='blank'>zur Faktorisierung] einer ganzen Zahl
*Berechnung des Multiplikation]
• Potenzieren]
*Berechnung des größten_gemeinsamen_Teilers mit Hilfe des Euklidischen_Algorithmus
*Berechnung des Jacobi-Symbols mit Hilfe des quadratischen_Reziprozitätsgesetztes
• von Polynomen], insbesondere auch schnelles Wurzelziehen
Neue Forschungsergebnisse zur algorithmischen Zahlentheorie werden unter anderem auf der zweijährig stattfindenden Konferenz ANTS (Algorithmic Number Theory Symposium) präsentiert.
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 hat 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)
Personen
• Brillhart]
• H. Lehmer]
• K. Lenstra]
• W. Lenstra] (jr.)
• S. Manasse]
• A. Morrison]
• Odlyzko]
• Pollard]
• Pomerance]
• Schroeppel]
• L. Selfridge]
Literatur
Otto Forster: Algorithmische Zahlentheorie. Vieweg, 1996, ISBN 3-528-06580-X
Henri Cohen: A Course in Computational Algebraic Number Theory. 4. Auflage. Springer, Berlin 2003, ISBN 3-540-55640-0
Richard E. Crandall, Carl Pomerance: Prime Numbers - A Computational Perspective. 2. Auflage. Springer, 2005 ISBN 0-387-25282-7
Weblinks
• 7th Algorithmic Number Theory Symposium ? Webauftritt zur Konferenz 2006
• History of ANTS ? Übersicht der bisher stattgefundenen ANTS-Konferenzen
