Das Buch richtet sich schon an interessierte Gymnasialschüler (innen), was bei Büchern mit einem aktuellen mathematischen Hintergrund ungewöhnlich ist. Primzahlen sind Gegenstand vieler mathematischer Probleme und spielen im Zusammenhang mit Verschlüsselungsmethoden eine wichtige Rolle. Im Jahr 2002 entwickelten die Informatiker Agrawal, Kayal und Saxena den jetzt nach ihnen benannten AKS-Algorithmus, den ersten deterministischen Primzahltest mit polynomieller Laufzeit. Das Buch leitet dieses bedeutende Resultat in einer verständlichen Art und Weise her, ohne wesentliche Vorkenntnisse zu benötigen. Es eignet sich außerdem von Studienbeginn an für Lehrveranstaltungen im Mathematik- oder Informatikstudium. Zu den einzelnen Abschnitten werden viele Aufgaben und weiterführende Anmerkungen gegeben, mit Lösungshinweisen am Ende des Buches.
Author(s): Lasse Rempe
Edition: 2010
Publisher: Vieweg+Teubner Verlag
Year: 2009
Language: German
Pages: 229
Cover......Page 1
Zahlentheorie – Algorithmik – Kryptographie......Page 4
ISBN 9783834806796......Page 5
Vorwort......Page 8
Inhalt......Page 10
Einleitung......Page 12
Teil I:
Grundlagen......Page 20
1.1 Die natürlichen Zahlen......Page 22
Aufgaben......Page 29
Weiterführende Übungen und Anmerkungen......Page 31
1.2 Teilbarkeit und Primzahlen......Page 32
1.3 Der Euklidische Algorithmus......Page 36
1.4 Primfaktorzerlegung......Page 40
1.5 Das Sieb des Eratosthenes......Page 43
1.6 Es gibt unendlich viele Primzahlen......Page 44
Weiterführende Literatur......Page 46
2.1 Algorithmen......Page 48
Aufgaben......Page 54
Weiterführende Übungen und Anmerkungen......Page 55
2.2 Algorithmisch lösbare und unlösbare Probleme......Page 56
Weiterführende Übungen und Anmerkungen......Page 60
2.3 Effizienz von Algorithmen und die Klasse P......Page 61
Aufgaben......Page 67
Weiterführende Übungen und Anmerkungen......Page 68
2.4 Wer wird Millionär? Die Klasse NP......Page 70
2.5 Randomisierte Algorithmen......Page 74
Aufgaben......Page 80
Weiterführende Übungen und Anmerkungen......Page 81
Weiterführende Literatur......Page 82
3.1 Modularrechnung......Page 84
Aufgaben......Page 90
Weiterführende Übungen und Anmerkungen......Page 91
3.2 Der kleine Satz von Fermat......Page 93
3.3 Ein erster Primzahltest......Page 102
3.4 Polynome......Page 104
Aufgaben......Page 113
Weiterführende Übungen und Anmerkungen......Page 114
3.5 Polynome und Modularrechung......Page 115
Aufgaben......Page 119
Weiterführende Übungen und Anmerkungen......Page 120
Weiterführende Literatur......Page 121
4.1 Kryptographie......Page 122
4.2 RSA......Page 125
Aufgaben......Page 127
Weiterführende Übungen und Anmerkungen......Page 128
4.3 Verteilung von Primzahlen......Page 129
Weiterführende Übungen und Anmerkungen......Page 131
4.4 Beweis des schwachen Primzahlsatzes......Page 132
Aufgaben......Page 134
4.5 Randomisierte Primzahltests......Page 135
Weiterführende Übungen und Anmerkungen......Page 140
Weiterführende Literatur......Page 141
Teil II:
Der AKS-Algorithmus......Page 142
5.1 Eine Verallgemeinerung des Satzes von Fermat......Page 144
Aufgaben......Page 148
Weiterführende Übungen und Anmerkungen......Page 149
5.2 Die Idee des AKS-Algorithmus......Page 150
5.3 Der Agrawal-Biswas-Test......Page 153
Kapitel 6
Der Satz von Agrawal, Kayal
und Saxena......Page 158
6.1 Die Aussage des Satzes......Page 159
6.2 Die Beweisidee......Page 160
Weiterführende Übungen und Anmerkungen......Page 161
6.3 Anzahl der Polynome in P......Page 162
6.4 Kreisteilungspolynome......Page 166
Aufgaben......Page 168
Weiterführende Übungen und Anmerkungen......Page 169
7.1 Wie schnell wächst ordr(n)?......Page 172
7.2 Der Algorithmus von Agrawal, Kayal und Saxena......Page 174
Aufgaben......Page 176
7.3 Weitere Anmerkungen......Page 177
Weiterführende Übungen und Anmerkungen......Page 179
Weiterführende Literatur......Page 180
Die Riemannsche Vermutung......Page 182
Die Goldbachsche Vermutung......Page 184
Primzahlzwillinge......Page 185
Mersenne-Zahlen......Page 187
Sophie-Germain-Primzahlen......Page 188
Fermat-Zahlen......Page 189
Weiterführende Übungen und Anmerkungen......Page 190
Weiterführende Literatur......Page 191
Anhang B Lösungen und Hinweise zu wichtigen Aufgaben......Page 192
Notationsverzeichnis......Page 218
Stichwortverzeichnis......Page 220
Literaturverzeichnis......Page 226
