Primzahltest
Als Primzahltest bezeichnet man ein mathematisches Verfahren, mit dem ermittelt wird, ob eine gegebene Zahl eine Primzahl ist oder nicht.In der Praxis werden Primzahltests insbesondere bei Verschlüsselungsverfahren in der Kryptographie eingesetzt. Algorithmen wie RSA benötigen Primzahlen in einer Größenordnung von etwa 1000 Stellen in binärer Darstellung. In diesem Bereich gibt es so viele Primzahlen, dass es nicht effizient wäre, diese in einer Liste zu speichern und bei Bedarf einfach darauf zuzugreifen. Auch aus sicherheitstechnischen Gründen ist dieser Ansatz nicht unbedingt empfehlenswert: potentielle Angreifer könnten sich die Struktur der Speicherung zunutze machen, wenn sie das Verschlüsselungsverfahren knacken wollen. 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.
Es gibt zahlreiche Ansätze für Primzahltests, von denen die meisten exponentielle oder subexponentielle Laufzeit haben und damit in der Praxis nur bedingt einsatzfähig sind:
Bekannte Primzahltest-Verfahren
Bei diesem Verfahren ist es nicht notwendig, irgend eine Primzahl zu kennen. Der "naive" Programmierer wird ein Programm folgender Art schreiben:
input n
composite=0
do i=2 to (n-1)
if (n mod i = 0) then composite = 1
end
if (composite = 0) then print n;' ist eine Primzahl'
input n
composite=0
wurzel_n=int(sqrt(n))
do i=2 to wurzel_n
if (n mod i = 0) then composite = 1
end
if (composite = 0) print n;' ist eine Primzahl'
primanzahl=1
primzahl.1 = 2
n=1000
print 2;' ist eine Primzahl'
do i1=3 to n
composite=0
do i2=1 to primanzahl
if (i1 mod primzahl.i2 = 0) then composite = 1
end
if (composite = 0) then do
primanzahl++
primzahl.primanzahl = i1
print i1;' ist eine Primzahl'
end
end
Das Siebverfahren unterscheidet sich von den anderen Verfahren, da es alle Primzahlen von 2 bis zu einer vorgegebenen Grenze heraus siebt, während die anderen Verfahren in der Lage sind, nur die einzelne Zahl auf ihre Primalität zu prüfen.
primzahlfeld:Array[2..10000] of integer;
n=10000
/*Initialisierung des Primzahlfeldes: Alle Zahlen größer gleich 2 sind Primzahlen */
do i=2 to n
primzahlfeld[i]=1
end
do i=2 to sqrt(n)
if (primzahlfeld[i]=1) then
do i2=i*i to n by i
primzahlfeld[i2]=0
end
end
do i=2 to n
if (primzahlfeld[i]=1) then print i;", ";
end
Der zum Fermatschen Primzahltest dazugehörige Quell-Code
- Der ARCL-Test ist eine Verbesserung des Fermatschen Primzahltests. Der Name besteht aus den Initialen der Mathematiker Leonard Adleman, R.S.Rumely, H.Cohen und H.W.Lenstra Jr.
- Der Lucas-Lehmer-Test zum Prüfen von Mersenne-Primzahlen.
- Der Miller-Rabin-Test, ein Monte-Carlo-Algorithmus, der durch die Randomisierung eine akzeptable Laufzeit erreicht, sowie schon nach wenigen Durchführungen mit hoher Wahrscheinlichkeit das korrekte Ergebnis gefunden hat.
- Der Solovay-Strassen-Test, ebenfalls ein Monte-Carlo-Algorithmus, bei dem aber im Allgemeinen die Anzahl der falschen Zeugen größer ist als beim Miller-Rabin-Test.
- 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 und
In der Komplexitätstheorie war das dem Primzahltest zugrundeliegende Problem, nämlich die Frage, ob eine Zahl prim ist, bis vor wenigen Jahren ein sehr interessanter Kandidat, von dem man sich neue Erkenntnisse für die offene Frage, ob gilt, erhoffte, da die Primzahltests sowohl in der Klasse NP als auch in der Klasse co-NP liegen, man aber keinen Algorithmus kannte, der in deterministisch in polynomieller Zeit arbeitete, also in der Klasse P liegt. Nun wurde 2002 von Agrawal, Kayal und Saxana ein solcher polynomieller Primzahltest, genannt AKS-Methode, gefunden, was einiges Aufsehen erregte, da die Fragestellung so lange offen war. Die Tatsache, dass es diesen Polynomizeit-Algorithmus gibt, hilft allerdings nicht bei der Beantwortung der -Frage weiter. Ebensowenig gefährdet er die Sicherheit von Verschlüsselungstechniken wie RSA: diese benötigen schnelle Primzahltests. Eine Gefährdung könnte lediglich von einem schnellen Faktorisierungsverfahren ausgehen, das aber bisher nicht gefunden wurde.