Wichtigste Bereiche der algorithmischen Zahlentheorie sind

• Tests zur Überprüfung der Primzahleigenschaft
• Verfahren zur Faktorisierung einer ganzen Zahl
• Berechnung des diskreten Logarithmus

• 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

Table of contents

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