Diskrete algebraische Methoden

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