In diesem Buch geht es um den AKS-Algorithmus, den ersten deterministischen Primzahltest mit polynomieller Laufzeit. Er wurde benannt nach den Informatikern Agrawal, Kayal und Saxena, die ihn 2002 entwickelt haben. Primzahlen sind Gegenstand vieler mathematischer Probleme und spielen im Zusammenhang mit Verschlüsselungsmethoden eine wichtige Rolle. Das vorliegende Buch leitet den AKS-ALgorithmus in verständlicher Art und Weise her, ohne wesentliche Vorkenntnisse zu benötigen, und ist daher
✦ Table of Contents
Front Matter....Pages i-xx
Front Matter....Pages 1-1
Natürliche Zahlen und Primzahlen....Pages 3-27
Algorithmen und Komplexität....Pages 29-63
Zahlentheoretische Grundlagen....Pages 65-102
Primzahlen und Kryptographie....Pages 103-122
Front Matter....Pages 123-123
Der Ausgangspunkt: Fermat für Polynome....Pages 125-138
Der Satz von Agrawal, Kayal und Saxena....Pages 139-151
Der Algorithmus....Pages 153-161
Anhang A: Offene Fragen über Primzahlen....Pages 163-173
Anhang B: Lösungen und Hinweise zu wichtigen Aufgaben....Pages 175-199
Back Matter....Pages 163-211
✦ Subjects
Number Theory; Data Encryption; Algebra; Algorithms