Primzahltests

Mit einem Primzahltest läßt sich feststellen, ob eine gegebene Zahl eine Primzahl ist oder eben nicht.

Bei den Primzahltest wird zwischen echten Tests und probabilistischen Test unterschieden. Mit den echten Test kann festgestellt werden, ob eine gegebene Zahl eine echte Primzahl ist.

Echte Primzahltest

Da eine Primzahl nur die beiden Teiler 1 und sich selbst besitzt, gibt es keine andere Möglichkeit, als alle möglichen Teiler auszuprobieren. Es müssen aber nicht alle möglichen Teiler ausprobiert werden. Mit Hilfe der folgenden Test, können mögliche Teiler einfacher gefunden werden.

Probedivision

Bei der Probedivision wird die gegebene Zahl n nacheinander durch alle Zahlen kleiner als n ganzzahlig ohne Rest teilbar ist. Dabei genügt es, nur Primzahlen zu nehmen, die kleiner als √n sind.

Sieb des Eratosthenes

Mit dem Sieb des Eratosthenes kann eine Liste von Primzahlen bis zu einer gegebenen Zahl erzeugt werden. Für einen Primzahltest genügt es nun zu überprüfen, ob die gesuchte Zahl in dieser Liste enthalten ist.

Sieb von Atkin

Das Sieb von Atkin ist ein moderner Algorithmus zur Bestimmung einer Liste von Primzahlen bis zu einer gegebenen Zahl. Er ist ein optimierter Algorithmus nach dem Sieb des Eratosthenes und schneller.
Bei kleineren Zahlen ist er etwas langsamer als das Sieb des Eratosthenes, wird im Vergleich dann aber bei größeren Zahlen schneller.

Probabilistische Primzahltests

Die probabilistischen Primzahltests beruhen auf dem kleinen fermatschen Satz und Folgerungen aus dem kleinen fermatschen Satz. Sie können nicht bestätigen, ob eine gegebene Zahl prim ist. Sie können aber mit einer gewissen Wahrscheinlichkeit garantieren, daß eine Zahl prim ist oder nicht.

Fermatscher Primzahltest

Dieser Primzahltest basiert auf dem kleinen fermatschen Satz und testet eine gegebene Zahl auf Fermatsche Pseudoprimzahlen.

Solovay-Strassen-Test

Dieser Test beruht auf dem Satz von Euler und dem Jacobi-Symbol. Mit ihm werden nacheinander alle Zahlen herausgesiebt, die weder Primzahlen noch Eulersche Pseudoprimzahlen sind. Mit Nutzung des Jacobi-Symbols fallen dann zusätzlich noch die Euler-Jacobi-Pseudoprimzahlen heraus.

Miller-Rabin-Test

Der Miller-Rabin-Test basiert auf dem Satz von Miller. Diesen Test bestehen nur Primzahlen und starke Pseudoprimzahlen.

Lucas-Test

Mit dem Lucas-Test können Fermat-Zahlen auf Prim-Eigenschaft geprüft werden.

Pépin-Test

Der Pépin-Test ist eine spezielle Version des Lucas-Test und dient auch zum Prüfen von Fermat-Zahlen.

Lucas-Lehmer-Test

Dieser Test eignet sich zum Prüfen von Mersenne-Primzahlen.

APRCL-Test

Dieser Test, der nach den Anfangsbuchstaben der Erfinder (Leonard Adleman, Carl Pomerance, Robert Rumely, Henri Cohen und Hendrik W. Lenstra Jr) benannt ist, ist eine Verbesserung des fermatschen Primzahltests.

AKS-Methode

Mit Hilfe dieser Methode kann in polynomieller Laufzeit festgestellt werden, ob eine gegebene Zahl prim ist oder nicht. Die Arbeit der Erfinder
Manindra Agrawal, Neeraj Kayal und Nitin Saxena wurde 2006 mit dem Gödel- und Fulkerson-Preis ausgezeichnet.