Die Arbeit thematisiert das Themenfeld der Primzahlen. Neben den von Euklid gezeigten Sätzen werden zu Beginn der Arbeit andere zentrale Aussagen der Zahlentheorie bewiesen. Das anschließende Kapitel liefert für den Spezialfall, dass N − 1 leicht faktorisierbar ist, durch die von Lucas und Proth entwickelten klassischen Primzahltests eine Antwort. Als eine Art Komplement dazu werden danach mithilfe von Lucas-Folgen Tests hergeleitet, welche die Kenntnis der Primfaktoren von N + 1 erfordern. Darüber hinaus werden zwei wichtige Teilfolgen von Lucas-Folgen, nämlich die Fermat-Zahlen und die Mersenne-Zahlen behandelt.
Des Weiteren werden zusammengesetzte Zahlen betrachtet, welche gewisse Eigenschaften mit den Primzahlen teilen. Wenn N keine spezielle Form aufweist, also weder N + 1 noch N − 1 leicht faktorisierbar sind, liefert das nächste Kapitel einen Test, dessen Idee auf elliptischen Kurven basiert. Dieser Algorithmus heißt Goldwasser-Kilian und ist der momentan schnellste allgemeine Primzahltest. Anschließend werden einige spezielle Primzahltypen vorgestellt.
Inhaltsverzeichnis
-
- Wichtige Eigenschaften von Primzahlen
- Das Sieb des Eratosthenes
- Der kleine Satz von Fermat
- Primitivwurzeln modulo einer Primzahl
- Der Satz von Wilson
- Primzahlpotenzen als Teiler der Fakultät einer Zahl
- Der chinesische Restsatz
- Die Eulersche p-Funktion
- Folgen von Binomialzahlen
- Quadratische Reste
- Klassische Primzahltests aufgrund von Kongruenzen
- Primzahltest von Proth
- Primzahltests von Lucas
- Implementierung von Proths Test
- Lucas-Folgen
- Definition und wichtige Spezialfälle
- Algebraische Fakten und Teilbarkeitseigenschaften
- Primzahltests auf der Grundlage von Lucas-Folgen
- Fermat-Zahlen
- Mersenne-Zahlen
- Pseudoprimzahlen
- Pseudoprimzahlen zur Basis 2 (psp)
- Pseudoprimzahlen zur Basis a (psp(a))
- Euler-Pseudoprimzahlen zur Basis a (epsp(a))
- Starke Pseudoprimzahlen zur Basis a (spsp(a))
- Carmichael-Zahlen
- Primzahlen und elliptische Kurven
- Elliptische Kurven
- Projektive Geometrie
- Der Goldwasser-Kilian Primzahltest
- Spezielle Primzahltypen
- Sophie-Germain-Primzahlen
- Wilson-Primzahlen
- Repunit-Primzahlen
- Primzahlen in arithmetischen Folgen
- Weitere Arten von Primzahlen
Zielsetzung und Themenschwerpunkte
Diese Diplomarbeit beschäftigt sich mit dem faszinierenden Bereich der Primzahlen. Sie beleuchtet verschiedene Aspekte dieser fundamentalen Zahlen, von ihren grundlegenden Eigenschaften bis hin zu speziellen Typen und deren Anwendung in der modernen Kryptographie.
- Erforschung von Eigenschaften und Algorithmen zur Identifizierung von Primzahlen
- Analyse verschiedener Primzahltests, darunter klassische Methoden und modernere Verfahren wie Lucas-Folgen und elliptische Kurven
- Untersuchung von speziellen Primzahltypen wie Sophie-Germain-Primzahlen, Wilson-Primzahlen und Repunit-Primzahlen
- Diskussion über die Rolle von Primzahlen in der modernen Kryptographie und ihre Anwendung in der Sicherheitstechnik
- Einblicke in die Geschichte und Entwicklung der Primzahlforschung
Zusammenfassung der Kapitel
Kapitel 1 legt die Grundlage für das Verständnis von Primzahlen. Es behandelt wichtige Eigenschaften, wie das Sieb des Eratosthenes, den kleinen Satz von Fermat, und den Satz von Wilson. Kapitel 2 befasst sich mit klassischen Primzahltests, insbesondere dem Proth-Test und den Lucas-Tests. Kapitel 3 konzentriert sich auf Lucas-Folgen, deren Eigenschaften und ihre Verwendung für Primzahltests. Es behandelt auch spezielle Fälle wie Fermat- und Mersenne-Zahlen. Kapitel 4 widmet sich Pseudoprimzahlen, verschiedenen Arten und ihren Eigenschaften. Kapitel 5 erforscht den Zusammenhang zwischen Primzahlen und elliptischen Kurven, einschließlich des Goldwasser-Kilian-Primzahltests. Schließlich behandelt Kapitel 6 verschiedene Spezialtypen von Primzahlen, wie Sophie-Germain-Primzahlen, Wilson-Primzahlen und Repunit-Primzahlen.
Schlüsselwörter
Primzahlen, Primzahltests, Kongruenzen, Lucas-Folgen, Pseudoprimzahlen, elliptische Kurven, Sophie-Germain-Primzahlen, Wilson-Primzahlen, Repunit-Primzahlen, Kryptographie, Sicherheitstechnik.
- Arbeit zitieren
- Peter Riesen (Autor:in), 2008, Primzahlen. Algorithmen, Charakterisierungen und spezielle Typen, München, GRIN Verlag, https://www.grin.com/document/916050
