Please use this identifier to cite or link to this item:
http://doi.org/10.25358/openscience-2841Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Hahn, Georg | |
| dc.date.accessioned | 2018-01-30T23:26:26Z | |
| dc.date.available | 2018-01-31T00:26:26Z | |
| dc.date.issued | 2018 | |
| dc.identifier.uri | https://openscience.ub.uni-mainz.de/handle/20.500.12030/2843 | - |
| dc.description.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. | de_DE |
| dc.language.iso | ger | |
| dc.rights | InCopyright | de_DE |
| dc.rights.uri | https://rightsstatements.org/vocab/InC/1.0/ | |
| dc.subject.ddc | 510 Mathematik | de_DE |
| dc.subject.ddc | 510 Mathematics | en_GB |
| dc.title | Polynomielle Primzahltests mit elliptischen Kurven | de_DE |
| dc.type | Masterarbeit | de_DE |
| dc.identifier.urn | urn:nbn:de:hebis:77-diss-1000018879 | |
| dc.identifier.doi | http://doi.org/10.25358/openscience-2841 | - |
| jgu.type.dinitype | masterThesis | |
| jgu.type.version | Original work | en_GB |
| jgu.type.resource | Text | |
| jgu.description.extent | 71 Seiten | |
| jgu.organisation.department | FB 08 Physik, Mathematik u. Informatik | - |
| jgu.organisation.year | 2011 | |
| jgu.organisation.number | 7940 | - |
| jgu.organisation.name | Johannes Gutenberg-Universität Mainz | - |
| jgu.rights.accessrights | openAccess | - |
| jgu.organisation.place | Mainz | - |
| jgu.subject.ddccode | 510 | |
| opus.date.accessioned | 2018-01-30T23:26:26Z | |
| opus.date.modified | 2018-02-15T10:53:18Z | |
| opus.date.available | 2018-01-31T00:26:26 | |
| opus.subject.dfgcode | 00-000 | |
| opus.organisation.string | FB 08: Physik, Mathematik und Informatik: Institut für Mathematik | de_DE |
| opus.identifier.opusid | 100001887 | |
| opus.institute.number | 0804 | |
| opus.metadataonly | false | |
| opus.type.contenttype | Prüfungsarbeit | de_DE |
| opus.type.contenttype | Examination Paper | en_GB |
| jgu.organisation.ror | https://ror.org/023b0x485 | |
| Appears in collections: | JGU-Publikationen | |
Files in This Item:
| File | Description | Size | Format | ||
|---|---|---|---|---|---|
 | 100001887.pdf | 543.4 kB | Adobe PDF | View/Open |