Detailansicht
A primality testing journey
the search for an unconditional deterministic polynomial-time algorithm
Milena Damrau
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Leonhard Summerer
DOI
10.25365/thesis.44656
URN
urn:nbn:at:at-ubw:1-10109.30628.571061-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Im August 2002 veröffentlichten Manindra Agrawal, Neeraj Kayal und Nitin Saxena, alle drei Informatiker und Mathematiker am "Indian Institute of Technology Kanpur", den ersten deterministischen Primzahltest mit polynomialer Laufzeit. Der sogenannte AKS Test war eine Sensation, denn bis zur Veröffentlichung war nicht bekannt, ob es überhaupt einen derartigen Primzahltest gibt. In der vorliegenden Arbeit machen wir eine Reise durch mehr als 2000 Jahre Primzahltests. Dabei werden wir die fundamentalsten und bekanntesten Primzahltests vorstellen - angefangen beim Sieb des Eratosthenes über Fermat, Miller-Rabin, Lucas und Primzahltests basierend auf elliptischen Kurven bis hin zum gefeierten AKS Test. Am Ende gehen wir der Frage nach, welcher Primzahltest für welchen Zweck verwendet werden sollte.
Abstract
(Englisch)
In 2002, the three Indian computer scientists M. Agrawal, N. Kayal and N. Saxena presented the first unconditional deterministic polynomial-time primality test. The so called AKS test. Until then, it was not even known, if such an algorithm exists. In this thesis, we will take a journey through more than 2000 years of primality testing and discuss the most fundamental and most popular primality testing algorithms - from the Sieve of Eratosthenes over Fermat, Miller-Rabin, Lucas and Elliptic Curve tests to the celebrated AKS test and its improvements. At the end we will discuss which primality test to use for what purpose.
Schlagwörter
Schlagwörter
(Englisch)
Prime numbers Primality test Elliptic curves Lucas Lucas-Lehmer AKS polynomial running time Time complexity analysis
Schlagwörter
(Deutsch)
Primzahlen Primzahltest Elliptische Kurven Lucas Lucas-Lehmer AKS polynomiale Laufzeit Laufzeitanalyse
Autor*innen
Milena Damrau
Haupttitel (Englisch)
A primality testing journey
Hauptuntertitel (Englisch)
the search for an unconditional deterministic polynomial-time algorithm
Paralleltitel (Deutsch)
Eine Primzahltest-Reise : die Suche nach einem bedingungslosen deterministischen Primzahltest mit polynomialer Laufzeit
Publikationsjahr
2016
Umfangsangabe
79 Seiten
Sprache
Englisch
Beurteiler*in
Leonhard Summerer
Klassifikation
31 Mathematik > 31.14 Zahlentheorie
AC Nummer
AC13734043
Utheses ID
39527
Studienkennzahl
UA | 066 | 821 | |