|
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 zur Faktorisierung einer ganzen
Zahl
- Berechnung des diskreten Logarithmus
Hierfür benötigt man weitere Verfahren, die ebenfalls untersucht werden:
- Schnelle
Multiplikation
- Schnelles
Potenzieren
- Berechnung des größten gemeinsamen
Teilers mit Hilfe des Euklidischen
Algorithmus
- Berechnung des Jacobi-Symbols mit Hilfe des quadratischen
Reziprozitätsgesetztes
- Faktorisierung von Polynomen, insbesondere auch schnelles
Wurzelziehen
| Inhaltsverzeichnis |
|
1 Anwendungen
2 Personen
3 Literatur
4 Weblinks
|
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 (d.i. 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/challenges/factoring/numbers.html)
Personen
- John Brillhart
- Derrick H. Lehmer
- Arjen K. Lenstra
- Hendrik W. Lenstra (jr.)
- Mark S. Manasse
- Michael A. Morrison
- Andrew Odlyzko
- John Pollard
- Carl Pomerance
- Richard Schroeppel
- John L. Selfridge
Literatur
- O. Forster, Algorithmische Zahlentheorie, Vieweg-Verlag, 1996
- H. Cohen, A Course in Computational Algebraic Number Theory (Graduate Texts in Mathematics, Vol 138), Springer
Verlag, 1996
- R. Crandell und C. Pomerance, Prime Numbers - A Computational Perspective, Springer Verlag, 2002
Weblinks
http://www.informatik.uni-trier.de/~ley/db/conf/ants/ (Algorithmic
Number Theory Symposium, ANTS)
|
