Primzahltest

Zweck und Bedeutung

Ein Primzahltest ist ein mathematisches Verfahren, das entscheidet, ob eine gegebene Zahl eine Primzahl ist oder nicht. Er ist besonders für asymmetrische Verschlüsselungsverfahren der Kryptographie wichtig: RSA benötigt Primzahlen von etwa 1000 Stellen in dualer Darstellung. Solche Primzahlen können nicht vollständig berechnet und gespeichert werden; auch eine vorberechnete Liste wäre sicherheitlich problematisch, falls sie Angreifern zugänglich würde. Deshalb wird eine „beliebige“ Zahl geraten und möglichst schnell auf Primzahleigenschaft geprüft.

Einfache Verfahren und Siebe

Bei der Probedivision wird geprüft, ob n durch eine Primzahl p mit 2 ≤ p ≤ √n teilbar ist. Gibt es keinen solchen Teiler, ist n prim. Praktisch wird dieses einfache Verfahren nur für kleine n bis etwa eine Million verwendet; bei größeren Zahlen sind andere Verfahren effizienter.

Das Sieb des Eratosthenes erzeugt alle Primzahlen bis zu einer frei wählbaren Grenze. Ein Test kann dann durch Nachschlagen erfolgen, ob die Zahl in dieser Liste steht. Für große Zahlen ist das Erzeugen und Verwenden einer solchen Liste jedoch zu aufwendig.

Das Sieb von Atkin bestimmt ebenfalls alle Primzahlen bis zu einer vorgegebenen Grenze und ist eine optimierte, moderne Version des Siebs des Eratosthenes. Bei einem kleinen Limit wie 100 ist es noch etwas langsamer, sein Zeitvorteil wächst aber mit dem Limit.

Probabilistische und spezielle Tests

Bei Zahlen der für Kryptographie benötigten Größe dauern „echte“ Primzahltests meist zu lange. Daher nutzt man oft Monte-Carlo-Algorithmen, also probabilistische Primzahltests. Sie liefern keine absolute Gewissheit, können aber die Wahrscheinlichkeit, eine zusammengesetzte Zahl fälschlich als prim einzustufen, beliebig klein machen. Dieses Restrisiko wird in Kauf genommen, obwohl eine Nicht-Primzahl als kryptographischer Schlüssel die Verschlüsselung unsicher machen würde.

Auf dem kleinen fermatschen Satz und Folgerungen daraus beruhen, in aufsteigender Stärke, der Fermatsche Primzahltest mit fermatschen Pseudoprimzahlen, der Solovay-Strassen-Test mit eulerschen Pseudoprimzahlen sowie der Miller-Rabin-Test mit starken Pseudoprimzahlen. Der Miller-Rabin-Test hat eine akzeptable Laufzeit. Für bestimmte Bereiche natürlicher Zahlen ist bekannt, wie viele der ersten Primzahlen als Basen genügen, damit er deterministisch, also mit sicherer Aussage, verwendet werden kann.

Weitere Tests auf dieser Grundlage sind der Lucas-Test und der speziellere Pépin-Test für Fermat-Zahlen sowie der Lucas-Lehmer-Test für Mersenne-Primzahlen. Der 1980 entwickelte APRCL-Test von Leonard Adleman, Carl Pomerance, Robert Rumely, Henri Cohen und Hendrik W. Lenstra Jr. schaltet fermatsche Pseudoprimzahlen aus und verbessert damit den fermatschen Primzahltest wesentlich.

AKS und Komplexitätstheorie

Die AKS-Methode ist ein 2002 von Manindra Agrawal, Neeraj Kayal und Nitin Saxena gefundener Primzahltest in Polynomialzeit. Damit wurde gezeigt, dass PRIMES in der Komplexitätsklasse P liegt. PRIMES bezeichnet in der Informatik das Entscheidungsproblem, ob eine Zahl prim ist.

Vor 2002 hoffte man, PRIMES könne für das P-NP-Problem neue Erkenntnisse liefern. Falls P≠NP gilt, muss nach dem Satz von Ladner ein Problem in NP\P existieren, das nicht NP-vollständig ist; PRIMES galt als möglicher Kandidat. Der Grund war, dass PRIMES sowohl in NP als auch in co-NP liegt und unter der gängigen Annahme P≠NP daher nicht NP-vollständig sein konnte. Vor 2002 war jedoch kein nicht-probabilistischer Algorithmus mit polynomieller Laufzeit bekannt.