Algorithmische Zahlentheorie
# 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

* Primzahltests
* 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ätsgesetzes
* Faktorisierung von Polynomen, insbesondere auch schnelles Wurzelziehen.

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

## Anwendungen

Die wichtigste Anwendung der algorithmischen Zahlentheorie ist die Kryptographie. Beispielsweise 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. Weiter Anwendung in der Kryptographie finden Algorithmen etwa bei der Berechnung von diskreten Logarithmen für andere Verschlüsselungs- und Signaturverfahren.

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

* Leonard Adleman
* A. O. L. Atkin
* Daniel Bernstein
* Jonathan Borwein
* Peter Borwein
* Richard P. Brent
* John Brillhart
* Johannes Buchmann
* Henri Cohen
* Allan Joseph Champneys Cunningham
* Noam Elkies
* Maurice Kraitchik
* Jeffrey Lagarias
* Derrick Henry Lehmer
* Emma Lehmer
* Arjen Lenstra
* Hendrik Lenstra (Jr.)
* Édouard Lucas
* Mark S. Manasse
* Preda Mihăilescu
* Victor S. Miller
* Peter Montgomery
* François Morain
* Andrew Odlyzko
* Michael Pohst
* John M. Pollard
* Carl Pomerance
* Hans Riesel
* René Schoof
* Richard Schroeppel
* John L. Selfridge
* Daniel Shanks
* Herman te Riele
* Samuel Wagstaff
* Hugh C. Williams
* Marvin Wunderlich
* Don Zagier
* Hans Zassenhaus
