Aktion	Zweigstelle	Standorte	Status	Frist	Vorbestellungen
Vorbestellen	Zweigstelle: 07., Urban-Loritz-Pl. 2a	Standorte: NN.MA Remp / College 6a - Naturwissenschaften	Status: Verfügbar	Frist:	Vorbestellungen: 0

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.

 

/ AUS DEM INHALT: / / /

Einleitung xi

I Grundlagen 1

 

1 Natürliche Zahlen und Primzahlen 3

1.1 Die natürlichen Zahlen 3

1.2 Teilbarkeit und Primzahlen 13

1.3 Der Euklidische Algorithmus 17

1.4 Primfaktorzerlegung 21

1.5 Das Sieb des Eratosthenes 24

1.6 Es gibt unendlich viele Primzahlen 25

 

2 Algorithmen und Komplexität 29

2.1 Algorithmen 29

2.2 Algorithmisch lösbare und unlösbare Probleme 37

2.3 Effizienz von Algorithmen und die Klasse P 42

2.4 Wer wird Millionär? Die Klasse NP 51

2.5 Randomisierte Algorithmen 55

 

3 Zahlentheoretische Grundlagen 65

3.1 Modularrechnung 65

3.2 Der kleine Satz von Fermât 74

3.3 Ein erster Primzahltest 83

3.4 Polynome 85

3.5 Polynome und Modularrechung 96

 

4 Primzahlen und Kryptographie 103

4.1 Kryptographie 103

4.2 RSA 106

4.3 Verteilung von Primzahlen 110

4.4 Beweis des schwachen Primzahlsatzes 113

4.5 Randomisierte Primzahltests 116

 

II Der AKS-Algorithmus 123

5 Der Ausgangspunkt: Fermât für Polynome 125

5.1 Eine Verallgemeinerung des Satzes von Fermât 125

5.2 Die Idee des AKS-Algorithmus 131

5.3 Der Agrawal-Biswas-Test 134

 

6 Der Satz von Agrawal, Kayal und Saxena 139

6.1 Die Aussage des Satzes 140

6.2 Die Beweisidee 141

6.3 Anzahl der Polynome in V 143

6.4 Kreisteilungspolynome 147

 

7 Der Algorithmus 153

7.1 Wie schnell wächst ordr(n)? 153

7.2 Der Algorithmus von Agrawal, Kayal und Saxena 155

7.3 Weitere Anmerkungen 158

 

A Offene Fragen über Primzahlen 163

B Lösungen und Hinweise zu wichtigen Aufgaben 173

Notationsverzeichnis 199

Stichwortverzeichnis 201

Literaturverzeichnis 207