Hintergrundwissen
Primzahltests
Primzahltests sind mathematische Verfahren, um zu entscheiden, ob eine gegebene natürliche Zahl eine Primzahl ist oder zusammengesetzt.
Eine Auswahl verschiedener Primzahltests:
- Alle potentiellen Teiler testen
- Sieb des Eratosthenes (*)
- Fermatscher Primzahltest
- Solovay-Strassen-Test
- Miller-Rabin Primzahltest
- AKS-Theorem: Polynomialer Primzahlnachweis
- (n+1)-Test
- Primzahltest mit elliptischen Kurven
(*) Das Sieb des Eratosthenes ist ein bekanntes Verfahren, um eine vollständige Liste von Primzahlen unterhalb einer vorher definierten (kleinen) Schranke zu erzeugen. Aus diesem Grunde ist es kein Primzahltest im eigentlichen Sinne. Es ist auch ungeeignet grosse Primzahlen zu erzeugen.