Zahlentheorie für Einsteiger

1 Vollständige Induktion.- 1.1 Das kleinste Element.- 1.2 Das Prinzip vom Maximum.- 1.3 Das Induktionsprinzip.- 1.4 Zusammenfassung.- 2 Euklidischer Algorithmus.- 2.1 Teilen mit Rest.- 2.2 Zahlen benennen. Stellenwertsysteme.- 2.3 Rechnen mit langen Zahlen.- 2.4 Der größte gemeinsame Teiler.- 2.5 Das Rechnen mit Kongruenzen.- 2.6 Ein wenig Geheimniskrämerei.- 2.7 Primzahlen.- 2.8 Ein kleiner Spaziergang zum Primzahlsatz.- 2.9 Der chinesische Restsatz.- 2.10 Die Euler-Funktion.- 3 Der kleine Fermatsche Satz.- 3.1 Kleiner Fermat.- 3.2 Die Ordnung einer Zahl modulo einer Primzahl.- 3.3 Primitivwurzeln.- 3.4 S. Germains Beitrag zum Problem von Fermat.- 3.5 Verschlüsseln mit dem Kleinen Fermat.- 3.6 Logarithmieren modulo p.- 3.7 Einheiten in Primpotenzmoduln.- 4 Die Jagd nach großen Primzahlen.- 4.1 Der negative Fermat-Test.- 4.2 Pseudoprimzahlen.- 4.3 Pseudoprimzahlen zur Basis a und Carmichael-Zahlen.- 4.4 Ein probabilistischer Primzahltest.- 4.5 Primzahltest von Miller und Rabin — Starke Pseudoprimzahlen.- 4.6 RSA-Verschlüsselung.- Stichwortverzeichnis.