Primzahltest

In der Praxis werden Primzahltests insbesondere Verschlüsselungsverfahren in der Kryptographie eingesetzt. Algorithmen wie RSA benötigen Primzahlen in einer Größenordnung von 1000 Stellen in binärer Darstellung. In diesem gibt es so viele Primzahlen dass es effizient wäre diese in einer Liste zu und bei Bedarf einfach darauf zuzugreifen. Auch sicherheitstechnischen Gründen ist dieser Ansatz nicht unbedingt potentielle Angreifer könnten sich die Strukur der zunutze machen wenn sie das Verschlüsselungsverfahren knacken Statt der Verwendung einer bekannten Primzahl rät Algorithmus (mit ein paar Tricks) eine "beliebige" und stellt mit Hilfe eines Primzahltests möglichst fest ob diese tatsächlich prim ist.

Bekannte Primzahltest-Verfahren

Es gibt zahlreiche Ansätze für Primzahltests von denen die meisten exponentielle oder Laufzeit haben und damit in der Praxis bedingt einsatzfähig sind:

• Das einfache Durchtesten auf Teilbarkeit .

Bei diesem Verfahren ist es nicht notwendig eine Primzahl zu kennen. Der "naive" Programmierer ein Programm folgender Art schreiben:

 input n composite=0 do i=2 to if (n mod i = 0) then = 1 end if (composite = 0) 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 Primzahl.

Dabei ist es gar nicht notwendig bis n-1 zu testen. Es reicht bis <math>\sqrt{n}</math> testen:

 input n composite=0 wurzel_n=int(sqrt(n)) do i=2 wurzel_n if (n mod i = 0) composite = 1 end if (composite = print n;' ist eine Primzahl'  

Warum <math>1<m\le\sqrt{n}</math> und nicht <math>1<m<n</math>?

Für eine zusammengesetzte Zahl n=n ₁ *n ₂ *... mit n ₁ <n ₂ <... reicht es aus zu zeigen das durch n ₁ teilbar ist. Im Extremfall bei einer Zahl mit zwei Primfaktoren n ₁ und n ₂ kann es sein das n ₁ = n ₂ ist. Dann trifft der Fall das = \sqrt{n}</math> ist zu. Ansonsten wird bei zusammengesetzen Zahl schon vor Erreichen von <math>\sqrt{n}</math> Teilbarkeit gefunden.

Auf dem Weg zum Sieb des Eratosthenes man folgendes machen:

 primanzahl=1 primzahl.1 = 2 n=1000 print ist eine Primzahl' do i1=3 to n do i2=1 to primanzahl if (n mod = 0) then composite = 1 end (composite = 0) then do primanzahl++ primzahl.primanzahl i1 print i1;' ist eine Primzahl' end  

• das Sieb des Eratosthenes das alle Primzahlen bis zu einer Schranke berechnet.
  Das Siebverfahren unterscheidet sich von den anderen da es alle Primzahlen von 2 bis einer vorgegebenen Grenze heraus siebt während die Verfahren in der Lage sind nur die Zahl auf ihre Primalität zu prüfen.

 primzahlfeld:Array[2..10000] of integer; n=10000 /*Initialisierung des Alle Zahlen größer gleich 2 sind Primzahlen do i=2 to n primzahlfeld[i]=1 end do to sqrt(n) if (primzahlfeld[i]=1) then do i2=i*i n by i primzahlfeld[i2]=0 end end do to n if (primzahlfeld[i]=1) then print i;" end  

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

• Der ARCL-Test ist eine Verbesserung des Fermatschen Der Name besteht aus den Initialen der Leonard A dleman R.S. R umely H. C ohen und H.W. L enstra Jr.

• Der Lucas-Lehmer-Test zum Prüfen von Mersenne-Primzahlen .

• den Miller-Rabin-Test einen Monte-Carlo-Algorithmus der durch die Randomisierung eine akzeptable erreicht sowie schon nach wenigen Durchführungen mit Wahrscheinlichkeit das korrekte Ergebnis gefunden hat

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

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

In der Komplexitätstheorie war das dem Primzahltest zugrundeliegende Problem die Frage ob eine Zahl prim ist vor wenigen Jahren ein sehr interessanter Kandidat dem man sich neue Erkenntnisse für die Frage ob <math>P \neq NP</math> gilt erhoffte da die Primzahltests sowohl der Klasse NP als auch in der Klasse co-NP man aber keinen Algorithmus kannte der in in polynomieller Zeit arbeitete also in der P liegt. Nun wurde 2002 von Agrawal Kayal und Saxana ein polynomieller Primzahltest genannt AKS-Methode gefunden was einiges erregte da die Fragestellung so lange offen Die Tatsache dass es diesen Polynomizeit-Algorithmus gibt allerdings nicht bei der Beantwortung der <math>P NP</math>-Frage weiter. Ebensowenig gefährdet er die Sicherheit von Verschlüsselungstechniken wie RSA: diese benötigen schnelle Primzahltests. Eine Gefährdung könnte lediglich einem schnellen Faktorisierungsverfahren ausgehen das aber bisher nicht gefunden

Bücher zum Thema Primzahltest

Dieser Artikel von Wikipedia unterliegt der GNU FDL.