Algorithmische Zahlentheorie / Algebra
Beschreibung
Das Ziel der algorithmischen Zahlentheorie besteht darin auf effiziente Weise Objekte zu berechnen, deren Existenz mithilfe der klassischen Zahlentheorie bewiesen wurde.
Zum Beispiel sagt uns ein berühmter Beweis von Euklid, dass es zu jeder gegebenen Zahl n eine Primzahl p gibt, die größer ist als n. Für den algorithmischen Zahlentheoretiker stellt sich hier die Frage: Wie finde ich möglichst schnell eine solche Primzahl?
Ein weiteres Beispiel gibt uns der Beweis des Fundamentalsatzes der Arithmetik, der sagt, dass es zu jeder Zahl n eine eindeutige Darstellung als Produkt von Primpotenzen existiert. Der algorithmische Zahlentheoretiker fragt hier: Kann ich die Primfaktorzerlegung von n schnell finden?
Entdeckungen
- 2005:
4181, die kleinste Frobenius Pseudoprimzahl bezüglich des Fibonacci-Polynoms x²-x-1
Eine elementare Herleitung für die effiziente Implementierung des Frobenius-Test nach Pommerance et al.
Literaturempfehlungen
Algorithmic Number Theory, Volume I: Efficient Algorithms
Bach, Shallit, 1996, MIT Press, ISBN 0-262-02405-5Prime Numbers - A Computational Perspective
Crandall, Pomerance, 2005², Springer Verlag, ISBN 0-387-25282-7