Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://doi.org/10.25358/openscience-2841
Autoren: Hahn, Georg
Titel: Polynomielle Primzahltests mit elliptischen Kurven
Online-Publikationsdatum: 31-Jan-2018
Erscheinungsdatum: 2018
Sprache des Dokuments: Deutsch
Zusammenfassung/Abstract: Mit dem Beweis des Mathematikers Euklid um 300 v. Chr. über die Existenz unendlich vieler Primzahlen beginnt die Suche nach effizienten Verfahren, um die Primalität von immer größeren Zahlen zu zeigen. Während es jedoch nach den Arbeiten von Fermat, Miller-Rabin und Solovay-Strassen relativ leicht ist, die Nicht-Primalität einer Zahl zu zeigen, blieben praktisch einsetzbare Primzahlbeweise, d.h. solche mit polynomieller Laufzeit, bis 2002 ein ungelöstes Problem. In diesem Jahr wurde mit dem Primzahltest nach Agrawal, Kayal und Saxena der erste Test vorgestellt, der beweisbar in polynomieller Zeit für alle Eingaben terminiert. Diese Arbeit behandelt polynomielle Primzahltests im Allgemeinen und den Test nach Goldwasser-Kilian im Speziellen, dessen theoretischer Hintergrund auf der Theorie der sogenannten elliptischen Kurven aufbaut. Zunächst werden polynomielle Tests anhand des Algorithmus von Agrawal-Kayal-Saxena in Kapitel 2 kurz eingeführt. Die Konzentration dieser Arbeit liegt jedoch auf den Tests von Goldwasser-Kilian und Atkin-Morain. Die dazu notwendige Theorie der elliptischen Kurven (elementare Definitionen, Gruppengesetz, Isogenien, elliptische Kurven über endlichen Körpern, Satz von Hasse u.a.) werden zusammen mit der Idee von Primalitätszertifikaten (insbesondere dem Pratt-Zertifikat) in Kapitel 3 behandelt. Dazu gehören auch der Satz von Goldwasser-Kilian sowie der daraus resultierende Primzahltest und dessen Korrektheit. Zudem beinhaltet diese Arbeit eine ausführliche Laufzeitbetrachtung, die auf der Vermutung von Goldwasser-Kilian über eine Abschätzung der Primzahlverteilung in Intervallen aufbaut. Eine Verbesserung des Goldwasser-Kilian Tests zum momentanen (Stand 2010) Standard "ECPP" (Elliptic Curve Primality Proving) wurde durch die Arbeiten von Atkin und Morain über die sogenannte Komplexe Multiplikation möglich. Diese Methode wird in Kapitel 4 zusammen mit ihrem theoretischen Hintergrund (elliptische Kurven über C, Weierstraß P-Funktion, j-Funktion, Fundamentaldiskriminanten, Hilbert'sche Klassenpolynome, Methode der Komplexen Multiplikation, Konstruktion elliptischer Kurven mit vorgegebener Ordnung u.a.) und dem verbesserten Test hergeleitet. Im Rahmen der Arbeit wurden beide Tests nach Goldwasser-Kilian und Atkin-Morain sowie eine Funktion zur Verifikation bereits erstellter Primalitätszertifikate für die Mathematiksoftware SAGE programmiert. Empirische Ergebnisse dazu folgen in Kapitel 5, die die polynomielle Laufzeit der Primzahltests demonstrieren. Die Arbeit schließt mit einer Diskussion der Ergebnisse und einem Ausblick im letzten Kapitel. Der Code für SAGE in der Programmiersprache Cython befindet sich im Anhang der Arbeit.
DDC-Sachgruppe: 510 Mathematik
510 Mathematics
Veröffentlichende Institution: Johannes Gutenberg-Universität Mainz
Organisationseinheit: FB 08 Physik, Mathematik u. Informatik
Veröffentlichungsort: Mainz
ROR: https://ror.org/023b0x485
DOI: http://doi.org/10.25358/openscience-2841
URN: urn:nbn:de:hebis:77-diss-1000018879
Version: Original work
Publikationstyp: Masterarbeit
Nutzungsrechte: Urheberrechtsschutz
Informationen zu den Nutzungsrechten: https://rightsstatements.org/vocab/InC/1.0/
Umfang: 71 Seiten
Enthalten in den Sammlungen:JGU-Publikationen

Dateien zu dieser Ressource:
  Datei Beschreibung GrößeFormat
Miniaturbild
100001887.pdf543.4 kBAdobe PDFÖffnen/Anzeigen