| Vorwort | 5 |
| 1 Algebraische Strukturen | 13 |
| 1.1 Gruppen | 16 |
| 1.2 Bewegungsgruppen regelmäßiger Vielecke | 23 |
| 1.3 Symmetrische Gruppen | 26 |
| 1.4 Ringe | 28 |
| 1.5 Modulare Arithmetik | 34 |
| 1.5.1 Der euklidische Algorithmus | 34 |
| 1.5.2 Ideale in den ganzen Zahlen | 36 |
| 1.5.3 Der chinesische Restsatz | 37 |
| 1.5.4 Die Euler’sche phi-Funktion | 38 |
| 1.6 Polynome und formale Potenzreihen | 39 |
| 1.7 Der Hilbert’sche Basissatz | 46 |
| 1.8 Körper | 47 |
| 1.9 Endliche Körper | 50 |
| 1.10 Die Einheitengruppe modulo n | 51 |
| 1.11 Das quadratische Reziprozitätsgesetz | 53 |
| Aufgaben | 56 |
| Zusammenfassung | 61 |
| 2 Kryptographie | 64 |
| 2.1 Symmetrische Verschlüsselungsverfahren | 64 |
| 2.2 Monoalphabetische Substitution | 67 |
| 2.3 Polyalphabetische Substitution | 69 |
| 2.4 Häufigkeitsanalyse und Koinzidenzindex | 70 |
| 2.5 Perfekte Sicherheit und Vernam-One-Time-Pad | 72 |
| 2.6 Asymmetrische Verschlüsselungsverfahren | 74 |
| 2.7 Das RSA-Kryptosystem | 76 |
| 2.8 Das Rabin-Kryptosystem | 77 |
| 2.9 Der Diffie-Hellman-Schlüsselaustausch | 78 |
| 2.10 Das ElGamal-Kryptosystem | 79 |
| 2.11 Das Merkle-Hellman-Kryptosystem und Shamirs Angriff | 81 |
| 2.12 Kryptographische Hashfunktionen | 87 |
| 2.13 Digitale Signaturen | 89 |
| 2.14 Teilen von Geheimnissen | 91 |
| 2.15 Elektronische Verpflichtung | 92 |
| Aufgaben | 94 |
| Zusammenfassung | 97 |
| 3 Zahlentheoretische Algorithmen | 99 |
| 3.1 Schnelle Exponentiation | 100 |
| 3.2 Probabilistische Primzahlerkennung | 102 |
| 3.2.1 Der Miller-Rabin-Primzahltest | 102 |
| 3.2.2 Der Solovay-Strassen-Primzahltest | 106 |
| 3.3 Faktorisierung ganzer Zahlen | 108 |
| 3.3.1 Pollards (p - 1)-Methode | 109 |
| 3.3.2 Pollards rho-Methode zur Faktorisierung | 109 |
| 3.4 Diskreter Logarithmus | 111 |
| 3.4.1 Shanks’ Babystep-Giantstep-Algorithmus | 112 |
| 3.4.2 Pollards rho-Methode für den diskreten Logarithmus | 112 |
| 3.4.3 Reduktion der Gruppenordnung nach Pohlig-Hellman | 114 |
| 3.5 Wurzelziehen in endlichen Körpern | 115 |
| 3.5.1 Der Algorithmus von Tonelli | 116 |
| 3.5.2 Der Algorithmus von Cipolla | 117 |
| 3.6 Multiplikation und Division | 118 |
| 3.7 Die diskrete Fourier-Transformation | 120 |
| 3.8 Primitive Einheitswurzeln | 123 |
| 3.9 Multiplikation nach Schönhage und Strassen | 123 |
| Aufgaben | 128 |
| Zusammenfassung | 130 |
| 4 Primzahlerkennung in Polynomialzeit | 132 |
| 4.1 Die Grundidee | 132 |
| 4.2 Technische Vorbereitungen | 133 |
| 4.3 Von kleinen Zahlen und großen Ordnungen | 136 |
| 4.4 Der Agrawal-Kayal-Saxena-Primzahltest | 136 |
| 5 Elliptische Kurven | 141 |
| 5.1 Gruppenstruktur | 145 |
| 5.1.1 Polynome über elliptischen Kurven | 147 |
| 5.1.2 Divisoren | 152 |
| 5.2 Anwendungen elliptischer Kurven | 154 |
| 5.2.1 Diffie-Hellman mit elliptischen Kurven | 155 |
| 5.2.2 Pseudokurven | 156 |
| 5.2.3 Faktorisierung mit elliptischen Kurven | 158 |
| 5.2.4 Primzahlzertifizierung nach Goldwasser-Kilian | 161 |
| 5.3 Endomorphismen elliptischer Kurven | 164 |
| Aufgaben | 168 |
| Zusammenfassung | 169 |
| 6 Kombinatorik auf Wörtern | 171 |
| 6.1 Kommutation, Transposition und Konjugation | 172 |
| 6.2 Der Satz von Fine und Wilf | 173 |
| 6.3 Kruskals Baumtheorem | 175 |
| Aufgaben | 180 |
| Zusammenfassung | 182 |
| 7 Automatentheorie | 183 |
| 7.1 Erkennbare Mengen | 184 |
| 7.2 Rationale Mengen | 191 |
| 7.3 Reguläre Sprachen | 197 |
| 7.4 Sternfreie Sprachen | 199 |
| 7.5 Das Krohn-Rhodes-Theorem | 203 |
| 7.6 Presburger-Arithmetik | 213 |
| 7.7 Automaten über unendlichen Wörtern | 217 |
| 7.7.1 Deterministische Büchi-Automaten | 218 |
| 7.7.2 Omega-rationale Ausdrücke | 220 |
| 7.7.3 Erkennbarkeit omega-regulärer Sprachen | 221 |
| Aufgaben | 225 |
| Zusammenfassung | 227 |
| 8 Diskrete unendliche Gruppen | 229 |
| 8.1 Das Wortproblem | 229 |
| 8.2 Ersetzungssysteme | 230 |
| 8.2.1 Termination und Konfluenz | 230 |
| 8.2.2 Semi-Thue-Systeme und Darstellungen von Monoiden | 233 |
| 8.3 Frei partiell kommutative Monoide und Graphgruppen | 236 |
| 8.4 Freie und semidirekte Produkte | 238 |
| 8.5 Amalgamierte Produkte und HNN-Erweiterungen | 240 |
| 8.6 Rationale Mengen und der Satz von Benois | 246 |
| 8.7 Freie Gruppen | 249 |
| 8.8 Die Automorphismengruppe freier Gruppen | 255 |
| 8.9 Die spezielle lineare Gruppe SL(2, Z) | 266 |
| Aufgaben | 271 |
| Zusammenfassung | 273 |
| Lösungen der Aufgaben | 277 |
| Literaturverzeichnis | 311 |
| Symbolverzeichnis | 315 |
| Index | 321 |
