A primality testing journey

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.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