Diskrete algebraische Methoden (eBook)

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Volker Diekert und Manfred Kufleitner, Universität Stuttgart; Gerhard Rosenberger, Universität Hamburg.

Volker Diekert und Manfred Kufleitner, University of Stuttgart, Germany; Gerhard Rosenberger, Universität Hamburg, Germany.

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