Primzahlen. Algorithmen, Charakterisierungen und spezielle Typen (PDF)

Diplomarbeit aus dem Jahr 2008 im Fachbereich Mathematik - Zahlentheorie, Note: 1,7, Universität zu Köln, Sprache: Deutsch, Abstract: 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.