Primzahltest

Ein Primzahltest ist ein mathematisches Verfahren, um festzustellen, ob eine gegebene Zahl eine Primzahl ist oder nicht.

Praktische Anwendung

In der Praxis werden Primzahltests insbesondere bei asymmetrischen Verschlüsselungsverfahren in der Kryptographie eingesetzt. Algorithmen wie RSA benötigen Primzahlen in einer Größenordnung von etwa 1000 Stellen in dualer Darstellung. Es ist also unmöglich, diese alle zu berechnen und in einer Liste zu speichern, um bei Bedarf einfach darauf zuzugreifen. Auch die Vorausberechnung einer Teilmenge ist aus sicherheitstechnischen Gründen fragwürdig, da die Liste Angreifern in die Hände fallen könnte. Statt der Verwendung einer bekannten Primzahl rät der Algorithmus (mit ein paar Tricks) eine „beliebige“ Zahl und stellt mit Hilfe eines Primzahltests möglichst schnell fest, ob diese tatsächlich prim ist.

Da „echte“ Primzahltests bei Zahlen dieser Größe zu lange dauern, wird meist ein Monte-Carlo-Algorithmus verwendet, mit dem in Wirklichkeit gar nicht mit absoluter Sicherheit festgestellt werden kann, ob die gegebene Zahl eine Primzahl ist (man spricht auch von probabilistischen Primzahltests). Es kann dabei aber die Wahrscheinlichkeit, eine zusammengesetzte Zahl fälschlicherweise für eine Primzahl zu halten, beliebig klein gemacht werden. Zwar würde die Verwendung einer Nicht-Primzahl als kryptographischer Schlüssel eine unsichere Verschlüsselung bedeuten, doch wenn die Wahrscheinlichkeit dafür milliardenmal geringer ist als die, dass Absender und Empfänger der Nachricht gleichzeitig vom Blitz getroffen werden, wird dieses Risiko in Kauf genommen, um das ansonsten sehr sichere Verschlüsselungsverfahren verwenden zu können.

Bekannte Primzahltest-Verfahren

Es gibt zahlreiche Ansätze für Primzahltests:

Probedivision

Hauptartikel: Probedivision

Der einfachste Primzahltest ist die Probedivision. Dabei probiert man nacheinander, ob die Zahl n durch eine der Primzahlen zwischen 2 und $\sqrt{n}$ teilbar ist. Ist sie das nicht, dann ist n eine Primzahl. Die Probedivision ist jedoch viel zu aufwändig, sodass sie in der Praxis als Primzahltest nicht zum Einsatz kommt.

Sieb des Eratosthenes

Hauptartikel: Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Algorithmus, der eine Liste von Primzahlen erzeugt. Da diese Liste bis zu einer frei wählbaren Grenze alle Primzahlen enthält, kann sie für einen Primzahltest verwendet werden. Man überprüft dazu, ob die übergegebene Zahl in der Liste ist. Auch dieses Verfahren ist für große Zahlen zu aufwändig und kann daher nicht als Primzahltest verwendet werden.

Sieb von Atkin

Hauptartikel: Sieb von Atkin

Das Sieb von Atkin ist ein schneller, moderner Algorithmus zur Bestimmung aller Primzahlen bis zu einer vorgegebenen Grenze. Es ist eine optimierte Version des antiken Sieb des Eratosthenes. Die Performance ist bei einem kleinen Limit von z.B. 100 noch etwas langsamer als bei dem Sieb des Eratosthenes, aber je größer das Limit, desto größer ist der Zeitvorteil gegenüber der alten Siebmethode.

Probabilistische Primzahltest

Die folgenden – in aufsteigender Stärke sortierten – Primzahltests beruhen auf dem kleinen fermatschen Satz und Folgerungen daraus:

Primzahltest	beruht auf	Art der auftretenden Pseudoprimzahlen
Fermatscher Primzahltest	kleiner Fermatscher Satz	Fermatsche Pseudoprimzahlen
Solovay-Strassen-Test	Satz von Euler und Jacobi-Symbol	Eulersche Pseudoprimzahlen
Miller-Rabin-Test	Satz nach Miller	starke Pseudoprimzahlen

Der Miller-Rabin-Test ist ein probabilistischer Primzahltest mit akzeptabler Laufzeit. Für gewisse Bereiche natürlicher Zahlen ist bekannt, wie viele der ersten Primzahlen als Basen benutzt werden müssen, um sogar eine sichere Aussage machen, den Algorithmus also deterministisch benutzen zu können (siehe Folge A014233 in OEIS).

Weitere Primzahltests, die auf dem kleinen fermatschen Satz beruhen

• Lucas-Test, und der speziellere Pépin-Test zum Prüfen von Fermat-Zahlen
• Lucas-Lehmer-Test zum Prüfen von Mersenne-Primzahlen
• APRCL-Test (der Name besteht aus den Initialen der Mathematiker Leonard Adleman, Carl Pomerance, Robert Rumely, Henri Cohen und Hendrik W. Lenstra Jr), eine weitere Verbesserung des fermatschen Primzahltests

AKS-Methode

Die AKS-Methode ist ein Primzahltest in Polynomialzeit, der im Jahr 2002 von Manindra Agrawal, Neeraj Kayal und Nitin Saxena gefunden und nach ihnen benannt wurde.

Primzahltests in der Komplexitätstheorie

Die dem Primzahltest zugrundeliegende Problemstellung, festzustellen, ob eine Zahl prim ist, wird in der Informatik als PRIMES bezeichnet. Bis ins Jahr 2002 erhoffte man sich in der Komplexitätstheorie von ihr neue Erkenntnisse in Bezug auf das P-NP-Problem. Falls P≠NP gilt, muss nach dem Satz von Ladner ein Problem in NP\P existieren, welches nicht NP-vollständig ist^[1]. PRIMES galt als ein potenzieller Kandidat für ein solches Problem.

Dies lag daran, dass PRIMES sowohl in der Komplexitätsklasse NP als auch in der Komplexitätsklasse co-NP liegt, und demnach nicht NP-vollständig sein konnte (unter der gängigen Annahme, dass P≠NP). Man kannte jedoch keinen nicht-probabilistischen Lösungsalgorithmus mit polynomieller Laufzeit. Daher war es fraglich, ob PRIMES auch in der Komplexitätsklasse P liegt.

2002 wurde jedoch von Agrawal, Kayal und Saxena mit dem AKS-Primzahltest ein solcher polynomieller Primzahltest gefunden. Damit war die lange Zeit offene Frage, ob PRIMES in P liegt, beantwortet. Dies brachte jedoch keine weitere Erkenntnis zum P-NP-Problem.

Quellen

1. ↑ R. E. Ladner: On the structure of polynomial time reducibility, J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM Eintrag.

Weblinks

• Ein Überblick über verschiedene Primzahltestverfahren von D. Bernstein (englisch)
• Ein Javascript-basierter Primzahltest von Arndt Brünner