Title
The complexity of prime number tests / Theres Steiner
Die Komplexität von Primzahltests
AuthorSteiner, Theres
CensorDrmota, Michael
PublishedWien, 2018
Description87 Seiten
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2018
Annotation
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
LanguageEnglish
Document typeThesis (Diplom)
Keywords (DE) Riemannsche Vermutung
Keywords (EN) Riemann hypothesis
URNurn:nbn:at:at-ubtuw:1-113099 Restriction-Information The work is publicly available
 Files The complexity of prime number tests [0.65 mb]
 Links Reference Universitätsbibliothek TU Wien
 Classification
 Abstract (English) Prime numbers have been a significant focus of mathematics throughout the years. Although the study of prime numbers may seem at first quite simple, perhaps because every schoolchild knows what a prime number is, the search for all of the secrets of prime numbers is far from over. Even one of the most famous, thus far unsolved, problems in mathematical history is directly linked to prime numbers, namely the Riemann Hypothesis. Until 2002, it was simply assumed that prime numbers can be differentiated from composites in polynomial time with a great deal of certainty; however, there was no definite proof to say this problem can be solved in polynomial time. If the General Riemann Hypothesis is true, though, some algorithms would classify as deterministic polynomial. If a counterexample for such an algorithm can be found, the test would not longer be classified as deterministic but rather probabilistic. In 2002, though, three Indian mathematicians developed a deterministic algorithm that runs in polynomial time; it is totally independent not only from the Riemann Hypothesis but also all other conjectures - the first of its kind. This result is, of course, groundbreaking for not only the specific field of number theory but also all of mathematics. The development of such an algorithm proves that the prime number problem can be deterministically solved in polynomial time. Additionally, following this initial discovery, further optimizations have been made by other researchers.
 Stats The PDF-Document has been downloaded 19 times.