Bibliographic Metadata

The complexity of prime number tests / Theres Steiner
Additional Titles
Die Komplexität von Primzahltests
AuthorSteiner, Theres
CensorDrmota, Michael
PublishedWien, 2018
Description87 Seiten
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2018
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
Document typeThesis (Diplom)
Keywords (DE)Primzahltest / Komplexität / Riemannsche Vermutung
Keywords (EN)primality test / complexity / Riemann hypothesis
URNurn:nbn:at:at-ubtuw:1-113099 Persistent Identifier (URN)
 The work is publicly available
The complexity of prime number tests [0.65 mb]
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.

The PDF-Document has been downloaded 19 times.