www.infos-aus-germanien.infoBy Germanien | Startseite | Impressum | Sitemap | Webtips
 

Primzahltest

www.infos-aus-germanien.info

Einordnung: Zahlentheorie

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.

Inhaltsverzeichnis
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 <math>P \neq NP<math>
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

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 <math>\sqrt{n}<math> 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 <math>1
Für eine zusammengesetzte Zahl n=n1*n2*... mit n1<n2<... reicht es aus, zu zeigen, das sie durch n1 teilbar ist. Im Extremfall, bei einer Zusammengesetzten Zahl mit zwei Primfaktoren n1 und n2, kann es sein, das n1 = n2 ist. Dann trifft der Fall, das <math>n_1 = \sqrt{n}<math> ist zu. Ansonsten wird, bei einer zusammengesetzen Zahl, schon vor Erreichen von <math>\sqrt{n}<math> eine Teilbarkeit gefunden, da entweder n1 oder n2 kleiner als <math>\sqrt{n}<math> 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

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

Der zum Fermatschen Primzahltest dazugehörige Quell-Code

Miller-Rabin

Solovay-Strassen

AKS-Methode

Primzahltests und <math>P \neq NP<math>

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 <math>P \neq NP<math> 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 <math>P \neq NP<math>-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







Info Hinweis: Dieser Artikel basiert auf dem Ursprungsartikel Primzahltest aus der Wiki pedia und er steht unter der GNU-Lizenz link fuer freie Dokumentation, eine Autoren-Liste ist ebenfalls verfuegbar.