E104 - Institut für Diskrete Mathematik und Geometrie
-
Date (published):
2008
-
Number of Pages:
90
-
Keywords:
Fermattests; Probabilistische Tests; Lucas-Lehmer-Tests; Primzahltest mit elliptischen Kurven; Primes in P
de
Abstract:
Diese Arbeit behandelt die gängigsten Methoden der Feststellung, ob eine Zahl eine Primzahl ist, ohne bestimmte Teiler der Zahl angeben zu müssen. Dabei geht man sowohl auf Tests für nur bestimmte Formate (z.B. Mersenne-Zahlen) als auch auf Tests für beliebige Zahlen ein; wichtige Rolle spielt dabei die Laufzeitbetrachtung. Es werden Möglichkeiten zur Angabe von Zeugen für die Zusammengesetztheit einer Zahl bzw. zur Angabe von Zertifikate für die Primalität einer Zahl angegeben. Des Weiteren werden die üblichsten Arten der probabilistischen Primzahltests behandelt.
