Diekert / Kufleitner / Rosenberger Diskrete algebraische Methoden

Arithmetik, Kryptographie, Automaten und Gruppen
1. Auflage 2013
ISBN: 978-3-11-031261-4
Verlag: De Gruyter
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Deutsch, 329 Seiten

Reihe: De Gruyter Studium

Bei diskreten algebraischen Methoden handelt es sich um ein zukunftsweisendes Gebiet, dessen Grundlagen weiter an Bedeutung gewinnen werden. Die Grundidee des vorliegenden Lehrbuchs ist, wesentliche Elemente der diskreten Mathematik zu vermitteln, um die modernen Entwicklungen im Informationszeitalter kompetent mathematisch beurteilen zu können. Es beginnt mit einem allgemeinen Kapitel über algebraische Strukturen, welches die Grundlage für das gesamte Buch bereitstellt. Das folgende Kapitel vermittelt Grundkenntnisse in Kryptographie. Kapitel 3 über zahlentheoretische Algorithmen ist wichtig für das Erzeugen von Kryptosystemen, für die beispielsweise große "zufällige" Primzahlen benötigt werden. In Kapitel 4 über Primzahlerkennung in Polynomialzeit stellen die Autoren den deterministischen Polynomialzeittest von Agrawal, Kayal und Saxena vor. Im folgenden Kapitel über elliptische Kurven stehen wieder die zahlentheoretischen und kryptographischen Anwendungen im Vordergrund. Mit den beiden Kapiteln "Kombinatorik auf Wörtern" und "Automatentheorie" begibt sich der Leser in das Teilgebiet der theoretischen Informatik, in dem die Halbgruppentheorie eine zentrale Rolle spielt. Das letzte Kapitel widmet sich diskreten unendlichen Gruppen. Das Buch ergänzt und vertieft Grundlagen und zeigt mögliche Anwendungen auf. Es werden aber auch Themen behandelt, die über den Standardstoff hinaus gehen. Einen hohen Stellenwert nehmen Aufgaben und Lösungen ein. Für alle wichtigen Aussagen geben die Autoren vollständige Beweise an. Am Ende eines jeden Kapitels sind kurze Kapitelzusammenfassungen als Lern- und Merkhilfe hinzugefügt. Das Buch wendet sich an Masterstudierende der Mathematik und Informatik mit fortgeschrittenen Kenntnissen in Mathematik. Die behandelten Grundlagen sind keine bloßen Aneinanderreihungen von Definitionen und elementaren Zusammenhängen. Das Buch vermittelt ein tieferes Verständnis für die behandelten mathematischen Zusammenhänge und stellt Wissen, Techniken und Denkweisen vor, welche den Leser in die Lage versetzen, selbstständig mathematische Probleme zu lösen.

Zielgruppe

Studierende, Dozenten; Akademische Bibliotheken

Autoren/Hrsg.

Diekert, Volker

Kufleitner, Manfred

Rosenberger, Gerhard

Fachgebiete

• Mathematik | Informatik Mathematik Algebra Algebraische Strukturen, Gruppentheorie
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

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

Über Autor(innen)

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.