Primzahltests auf Kommutatorkurven

Abstract

Das Thema dieser Dissertation sind effiziente Primzahltests. Zunächst wird die Kommutatorkurve eingeführt, die durch einen skalaren Parameter in der zweidimensionalen speziellen linearen Gruppe bestimmt wird. Nach Erforschung der Grundlagen dieser Kurve wird sie in verschiedene Pseudoprimzahltests (z.B. Fermat-Test, Solovay-Strassen-Test) eingebunden. Als wichtigster Pseudoprimzahltest ist dabei der Kommutatorkurventest zu nennen. Es wird bewiesen, dass dieser Test nach einer festen Anzahl von Probedivisionen (alle Primzahlen kleiner 80) das Ergebnis 'wahr' für eine zusammengesetzte Zahl mit einer Wahrscheinlichkeit ausgibt, die kleiner als 1/16 ist. Darüberhinaus wird bewiesen, dass der Miller-Primzahltest unter der Annahme der Korrektheit der Erweiterten Riemannschen Hypothese zur Überprüfung einer Zahl n nur noch für alle Primzahlbasen kleiner als 3/2*ln(n)^2 durchgeführt werden muss. Im Beweis des Primzahltests von G. L. Miller konnte dabei die Notwendigkeit der Erweiterten Riemannschen Hypothese auf nur noch ein Schlüssellemma eingegrenzt werden.

This thesis is about efficient primality tests. First, the commutator curve which is described by one scalar parameter in the two-dimensional special linear group will be introduced. After fundamental research of of this curve, it will be included into different compositeness tests (e.g. Fermat's test, Solovay-Strassen test). The most important commutator test is the Commutator Curve Test. Besides, it will be proved that this test after a fixed number of trial divisions (all prime numbers up to 80) returns the result 'true' for a composite number with a probability less than 1/16. Moreover, it will be shown that Miller's test to check a number n only has to be carried out for all prime bases less than 3/2*ln(n)^2. This happens under the assumption that the Extended Riemann Hypothesis is true. The necessity of the Extended Riemann Hypothesis to prove the primality test of G. L. Miller can be reduced to a single key lemma.