✍ Scribed by Otto Forster (auth.)
No coin nor oath required. For personal study only.
Das Buch gibt eine Einführung in die Zahlentheorie bis hin zu den quadratischen Zahlkörpern. Dabei wird durchgehend auch der algorithmische Aspekt betrachtet. So werden Existenzsätze (z.B. für die Darstellung von Primzahlen der Form p=4n+1 als Summe von zwei Quadratzahlen) stets durch Algorithmen zur Konstruktion ergänzt. Neben den klassischen Inhalten der elementaren Zahlentheorie werden in dem Buch u.a. auch die Multiplikation großer ganzer Zahlen mittels der schnellen Fourier-Transformation sowie Faktorisierung ganzer Zahlen mit elliptischen Kurven behandelt.
Für die Neuauflage wurden bekannt gewordene Fehler der ersten Auflage korrigiert und an mehreren Stellen Umarbeitungen vorgenommen. Außerdem gibt es neue Abschnitte über die Faktorisierung mit dem Quadratischen Sieb, den Diskreten Logarithmus (der in der Kryptographie eine große Rolle spielt) sowie über den deterministischen AKS-Primzahltest mit polynomialer Laufzeit. Damit der Leser die Algorithmen auf seinem Laptop oder PC auch konkret testen kann, werden die Algorithmen in einem pascalähnlichen Code für den vom Autor entwickelten Multipräzisions-Interpreter ARIBAS beschrieben, der zum kostenlosen Download zur Verfügung steht.
Front Matter....Pages i-viii
Die Peano-Axiome....Pages 1-8
Die Grundrechnungs-Arten....Pages 9-15
Die Fibonacci-Zahlen....Pages 16-21
Der Euklidische Algorithmus....Pages 22-31
Primfaktor-Zerlegung....Pages 32-43
Der Restklassenring Z/mZ....Pages 44-52
DieSätze von Fermat, Euler und Wilson....Pages 53-57
Die Struktur von (Z/mZ)., Primitivwurzeln....Pages 58-66
Pseudo-Zufalls-Generatoren....Pages 67-72
Zur Umkehrung des Satzes von Fermat....Pages 73-79
Quadratische Reste, quadratisches Reziprozitätsgesetz....Pages 80-91
Probabilistische Primzahltests....Pages 92-98
Die Pollard’sche Rho-Methode....Pages 99-106
Die (p-1)-Faktorisierungs-Methode....Pages 107-115
Das RSA-Kryptographie-Verfahren....Pages 116-122
Quadratische Erweiterungen....Pages 123-132
Der (p+1)-Primzahltest, Mersenne’sche Primzahlen....Pages 133-140
Die (p+1)-Faktorisierungs-Methode....Pages 141-146
Schnelle Fourier-Transformation....Pages 147-162
Faktorisierung mit dem quadratischen Sieb....Pages 163-183
Der diskrete Logarithmus....Pages 184-198
Elliptische Kurven....Pages 199-211
Faktorisierung mit elliptischen Kurven....Pages 212-220
Quadratische Zahlkörper....Pages 221-229
Der Vier-Quadrate-Satz von Lagrange....Pages 230-238
Kettenbrüche....Pages 239-252
Die Pell’sche Gleichung....Pages 253-261
Idealklassen quadratischer Zahlkörper....Pages 262-277
Faktorisierung mit der Klassengruppe....Pages 278-286
Der AKS-Primzahltest....Pages 287-301
Back Matter....Pages 302-314
Algorithms; Number Theory
📜 SIMILAR VOLUMES
<p>Dr. Otto Forster ist Professor am Mathematischen Institut der Ludwig-Maximilians-Universität München und Autor der bekannten Lehrbücher Analysis 1-3.</p>