Primzahltest Bedeutung, Erklärung und Definition.

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.

Table of contents

1 Bekannte Primzahltest-Verfahren 1.1 Einfaches Durchtesten 1.2 Sieb des Eratosthenes 1.3 Fermatscher Primzahltest 1.4 Miller-Rabin 1.5 Solovay-Strassen 1.6 AKS-Methode 2 Primzahltests und 3 Weblinks

Bekannte Primzahltest-Verfahren

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:

Einfaches Durchtesten

• Das einfache Durchtesten auf Teilbarkeit (Brute Force).

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'

Dabei prüft man bei einer Zahl n, ob sie durch eine natürliche Zahl m zwischen 2 und n-1 teilbar ist. Ist n durch kein m teilbar, so handelt es sich um eine Primzahl.

Dabei ist es gar nicht notwendig, bis n-1 zu testen. Es reicht, bis zu testen:

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'

Warum und nicht ?

Für eine zusammengesetzte Zahl n=n₁*n₂*... mit n₁2<... reicht es aus, zu zeigen, das sie durch n₁ teilbar ist. Im Extremfall, bei einer Zusammengesetzten Zahl mit zwei Primfaktoren n₁ und n₂, kann es sein, das n₁ = n₂ ist. Dann trifft der Fall, das ist zu. Ansonsten wird, bei einer zusammengesetzen Zahl, schon vor Erreichen von eine Teilbarkeit gefunden, da entweder n₁ oder n₂ kleiner als ist.

Auf dem Weg zum Sieb des Eratosthenes kann man folgendes machen:

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

Wie funktioniert dieses Programm? Im Programm wird eine Schleife von 3 bis zu einer Obergrenze, in diesem Fall 1000, durchlaufen, und getestet, ob eine Zahl durch die bisher gefundenen Primzahlen teilbar sind. Ist eine Zahl durch keine der bisher gefundenen Zahlen teilbar, dann ist sie selbst eine Primzahl, und wird zu den bisher gefundenen Primzahlen hinzugefügt. Zuerst hat man nur eine Primzahl, nämlich die 2.

Sieb des Eratosthenes

• das Sieb des Eratosthenes, das alle Primzahlen bis zu einer gegebenen Schranke berechnet.
  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

Fermatscher Primzahltest

• den Fermatschen Primzahltest, der allerdings nur dann Primzahlen von Pseudoprimzahlen mit 100%iger Sicherheit unterscheiden kann, wenn er zu jeder zu prüfenden Zahl alle möglichen Primbasen durchprüft, die kleiner als die zu prüfende Zahlen sind. Damit ist dieses Verfahren das langsamste Verfahren.
  

Der zum Fermatschen Primzahltest dazugehörige Quell-Code

• Der Lucas-Test ist eine Verbesserung des Fermatschen Primzahltest.

• 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.

Miller-Rabin

• 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.

Solovay-Strassen

• 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.

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 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 ihn 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 dem RSA- oder Rabin-Kryptosystem: diese benötigen schnelle Primzahltests (vgl. Faktorisierungsproblem). Eine Gefährdung könnte lediglich von einem schnellen Faktorisierungsverfahren ausgehen, das aber bisher nicht gefunden wurde.

Weblinks

• Ein Ãœberblick über verschiedene Primzahltestverfahren von D. Bernstein (engl.)

Diese Seite ist ein Artikel über Primzahltest. Seite Versuche, zum von von Beschreibung über bereitzustellen Primzahltest. Sie konnten Tatsachen über auch finden Primzahltest. Erklärung von Primzahltest.