Primzahltests für Einsteiger: Zahlentheorie - Algorithmik - Kryptographie

Cover......Page 1
Zahlentheorie – Algorithmik – Kryptographie......Page 4
ISBN 9783834806796......Page 5
Vorwort......Page 8
Inhalt......Page 10
Einleitung......Page 12
Teil I:\rGrundlagen......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:\rDer 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\rDer Satz von Agrawal, Kayal\rund 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