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
1 Grundlagen zu Primzahlen und Kongruenzen
1.1 Wichtige Eigenschaften von Primzahlen
1.2 Das Sieb des Eratosthenes
1.3 Der kleine Satz von Fermat
1.4 Primitivwurzeln modulo einer Primzahl
1.5 Der Satz von Wilson
1.6 Primzahlpotenzen als Teiler der Fakultät einer Zahl
1.7 Der chinesische Restsatz
1.8 Die Eulersche φ-Funktion
1.9 Folgen von Binomialzahlen
1.10 Quadratische Reste
2 Klassische Primzahltests aufgrund von Kongruenzen
2.1 Primzahltests von Lucas
2.2 Primzahltest von Proth
2.3 Implementierung von Proths Test
3 Lucas-Folgen
3.1 Definition und wichtige Spezialfälle
3.2 Algebraische Fakten und Teilbarkeitseigenschaften
3.3 Primzahltests auf der Grundlage von Lucas-Folgen
3.4 Fermat-Zahlen
3.5 Mersenne-Zahlen
4 Pseudoprimzahlen
4.1 Pseudoprimzahlen zur Basis 2 (psp)
4.2 Pseudoprimzahlen zur Basis a (psp(a))
4.3 Euler-Pseudoprimzahlen zur Basis a (epsp(a))
4.4 Starke Pseudoprimzahlen zur Basis a (spsp(a))
4.5 Carmichael-Zahlen
5 Primzahlen und elliptische Kurven
5.1 Elliptische Kurven
5.2 Projektive Geometrie
5.3 Der Goldwasser-Kilian Primzahltest
6 Spezielle Primzahltypen
6.1 Sophie-Germain-Primzahlen
6.2 Wilson-Primzahlen
6.3 Repunit-Primzahlen
6.4 Primzahlen in arithmetischen Folgen
6.5 Weitere Arten von Primzahlen
Zielsetzung und Themen
Die vorliegende Arbeit untersucht theoretische Grundlagen, Algorithmen und spezielle Klassifizierungen von Primzahlen, um die Primzahltests für natürliche Zahlen zu analysieren und weiterzuentwickeln.
- Mathematische Grundlagen und Kongruenzen
- Klassische und moderne Primzahltests (Lucas, Proth, Goldwasser-Kilian)
- Analyse von Lucas-Folgen und deren Anwendung
- Untersuchung von Pseudoprimzahlen und speziellen Primzahltypen
Auszug aus dem Buch
1.1 Wichtige Eigenschaften von Primzahlen
Definition 1.1 (Primzahl) Eine natürliche Zahl n ∈ N heisst Primzahl, wenn sie genau zwei positive Teiler hat, nämlich 1 und n.
Der folgende Satz erklärt den multiplikativen Aufbau der natürlichen Zahlen aus Primzahlen:
Satz 1.1 (Fundamentalsatz der Arithmetik) Jede von 1 verschiedene natürliche Zahl n ist als Produkt endlich vieler Primzahlen darstellbar; diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig.
Existenzbeweis: Ist n Primzahl, so ist nichts weiter zu tun, insbesondere ist damit der Induktionsanfang n = 2 erledigt. Sei nun n ∈ N, n > 2 und es werde die Existenz einer Zerlegung für alle m ∈ {2, ..., n − 1} vorausgesetzt. O.B.d.A. darf angenommen werden, dass n zusammengesetzt ist. Der kleinste positive Teiler p(n) von n ist offenbar eine Primzahl. Schreibt man nun n = m * p(n), ergibt sich m ∈ {2, ..., n − 1}; also existiert eine Produktdarstellung aus Primzahlen für m und somit auch für n.
Zusammenfassung der Kapitel
1 Grundlagen zu Primzahlen und Kongruenzen: Vermittlung mathematischer Grundlagen wie der Fundamentalsatz der Arithmetik, Eratosthenes-Sieb und wichtige Sätze wie Fermat und Wilson.
2 Klassische Primzahltests aufgrund von Kongruenzen: Vorstellung historischer und klassischer Primzahltests basierend auf Kongruenzsätzen.
3 Lucas-Folgen: Detaillierte mathematische Analyse der Lucas-Folgen und deren Nutzung für Primzahltests.
4 Pseudoprimzahlen: Untersuchung von Zahlen, die Eigenschaften von Primzahlen erfüllen, ohne tatsächlich prim zu sein.
5 Primzahlen und elliptische Kurven: Einführung in die Nutzung elliptischer Kurven zur Primzahlbestimmung, inklusive des Goldwasser-Kilian-Tests.
6 Spezielle Primzahltypen: Übersicht über besondere Arten wie Sophie-Germain-, Wilson-, Repunit- und palindromische Primzahlen.
Schlüsselwörter
Primzahlen, Zahlentheorie, Kongruenzen, Primzahltest, Lucas-Folgen, Pseudoprimzahlen, Elliptische Kurven, Fermat-Satz, Proth-Test, Goldwasser-Kilian, Carmichael-Zahlen, Sophie-Germain-Primzahlen, Repunit, Arithmetische Folgen
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit?
Die Arbeit befasst sich mit der mathematischen Theorie der Primzahlen, analysiert verschiedene Algorithmen zu ihrer Identifikation und kategorisiert spezielle Primzahltypen.
Welche Themenfelder werden zentral behandelt?
Die zentralen Felder umfassen elementare Zahlentheorie, komplexe Primzahltests, die Theorie der Lucas-Folgen sowie die Anwendung elliptischer Kurven in der Kryptographie bzw. im Primzahlnachweis.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist die theoretische Aufarbeitung und algorithmische Darstellung von Methoden, mit denen die Primalität natürlicher Zahlen effizient geprüft werden kann.
Welche wissenschaftlichen Methoden werden angewendet?
Die Arbeit nutzt beweisbasierte Ansätze der analytischen Zahlentheorie, algebraische Manipulationen von Lucas-Folgen und algorithmische Implementierungsbeispiele.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die mathematischen Grundlagen, klassische Kongruenztests, die Theorie der Lucas-Folgen, die Analyse von Pseudoprimzahlen sowie fortgeschrittene Verfahren mittels elliptischer Kurven.
Durch welche Schlüsselwörter lässt sich die Arbeit beschreiben?
Die wichtigsten Schlagworte sind Primzahltest, Zahlentheorie, Kongruenzen, Lucas-Folgen, elliptische Kurven und Pseudoprimzahlen.
Wie werden Lucas-Folgen in dieser Arbeit für Primzahltests genutzt?
Lucas-Folgen werden als Basis für Testalgorithmen verwendet, indem spezifische Teilbarkeitseigenschaften der Folgenglieder genutzt werden, um die Primalität von Zahlen wie N = k*2^n+1 zu verifizieren.
Warum ist der Goldwasser-Kilian-Test für die Arbeit relevant?
Er repräsentiert einen modernen und effizienten algorithmischen Ansatz, der auf elliptischen Kurven über endlichen Körpern basiert und damit über klassische Kongruenztests hinausgeht.
- Arbeit zitieren
- Peter Riesen (Autor:in), 2008, Primzahlen. Algorithmen, Charakterisierungen und spezielle Typen, München, GRIN Verlag, https://www.grin.com/document/916050
