Einleitung
Primzahlen sind Zahlen, die genau zwei Teiler haben. Der Abstand von Primzahlen wird anfangs mit größer werdendem Zahlenbereich immer größer, jedoch schwankt dieser Abstand später. Möchte man nun wissen, ob eine sehr große Zahl prim ist, gibt es verschiedene Primzahltestverfahren, um dies herauszufinden.
In der Praxis werden solch große Primzahlen für die Schlüsselerstellung bei asymmetrischen Verschlüsselungsverfahren wie z.B. RSA benötigt. Je größer die verwendeten Primzahlen sind, desto sicherer werden die Schlüssel. Somit ist es sinnvoll ein Verfahren zu nutzen, dass die generierten Zahlen auf Primalität prüft, um somit zu sichern, dass es sich um Primzahlen handelt.
Beweis der Existenz von unendlich vielen Primzahlen
Sollte es eine endliche Menge an Primzahlen geben, so könnte beim Testen einer Zahl auf prim geprüft werden, ob sich die zu testende Zahl in dieser Menge befindet. Folgender Beweis zeigt, dass dieser Ansatz nicht funktionieren kann, da es unendliche viele Primzahlen gibt.
Annahme: Es gibt endliche viele Primzahlen p1, p2, …, pn.
Dann lässt sich eine neue Zahl pneu = (p1*p2*p3…*pn)+1 konstruieren.
Nun gibt es zwei Möglichkeiten:
- q ist eine Primzahl, womit die obige Aussage falsch ist.
- q ist keine Primzahl. q ist somit durch keine Primzahl p1 … pn teilbar, da jedes pneu, i <= n, bei der Division den Rest 1 gibt. Somit gibt es auch keine anderen Teiler, da jede Zahl nach dem Prinzip der Primfaktorzerlegung durch ein Produkt aus Primzahlen dargestellt werden kann. Somit wurde eine neue Primzahl gefunden und obige Annahme ist wieder falsch.
Daraus folgt: Es gibt unendlich viele Primzahlen. Die höchste bisher gefundene Primzahl ist 243.112.609-1. Diese Zahl hat 12.978.189 Stellen und wurde im Jahr 2008 von Smith, Woltman & Kurowski (GIMPS) gefunden.
Sieb des Eratosthenes (nach Eratosthenes von Kyrene)
Dieser Algorithmus ermittelt Primzahlen durch systematisches Ausschließen von Vielfachen einer Primzahl. Definiert wird ein Zahlenbereich von zwei bis zu einer oberen Schranke Smax. Die kleinste, nicht ausgeschlossene Zahl ist immer eine Primzahl. Nun werden nacheinander alle vielfachen dieser Primzahl ausgeschlossen, beginnend mit dem Quadrat dieser Zahl, da alle vorhergehenden Zahlen schon ausgeschlossen wurden. Die nun niedrigste, nicht ausgeschlossene Zahl ist die nächste Primzahl und der Vorgang wird mit dieser Zahl wiederholt. Liegt das Quadrat einer zu betrachtenden Primzahl über Smax, so sind alle restlichen, nicht ausgeschlossenen Zahlen Primzahlen. Da dieser Algorithmus alle Vielfachen einer Primzahl prüft, arbeitet er äußerst langsam.
Fermatscher Primzahltest
Kleiner Fermatscher Satz: an-1 ≡ (mod n) für a ∈ [2,n-1], wenn n prim ist
Dieser Primzahltest liefert allerdings auch sog. Pseudoprimzahlen. Dies sind zusammengesetzte Zahlen, die für die pro gewählter Basis a verschieden sind (z.B. für a = 2 die 341). Führt man den Test für mehrere Basen a durch, kann man diese Pseudoprimzahlen ausschließen. Allerdings würden dann immer noch die sog. Carmichael-Zahlen den Primzahltest bestehen. Carmichael-Zahlen sind zusammengesetzte Zahlen aus Primzahlen (mindestens drei). Der fermatsche Primzahltest liefert nur für die Teiler einer Carmichael-Zahl als Basis a das korrekte Ergebnis. Für alle anderen Basen würde eine Carmichael-Zahl den Test bestehen. Man müsste folglich sämtliche Primbasen kleiner als n prüfen, was sehr unperformant ist. Der Beweis des kleinen Fermatschen Satzes kann unter http://www.arndt-bruenner.de/mathe/Allgemein/fermatklein.htm (20.10.2009) eingesehen werden.
Miller-Rabin Primzahltest
Der Miller-Rabin Primzahltest ist ein Monte-Carlo Algorithmus, d.h. er basiert, wie auch der Fermatsche Primzahltest, auf dem Zufall. Jedoch stellt der Miller-Rabin Primzahltest strengere Testkriterien und liefert so nur noch starke Pseudoprimzahlen. Die Wahrscheinlichkeit eine solche zu treffen ist geringer als beim Fermatschen Primzahltest. Der Algorithmus: Zu testen ist die Zahl n, die ungerade ist. Wähle nun ein a mit a ∈ [2, n-1]. Somit lassen sich ein u und ein t finden, für die gilt: u*2t= n – 1
Berechne alle au*2i mod n für i ∈ [0,t]. Hier ergibt sich eine Folge von Zahlen.
Das letzte Glied dieser Folge ist au*2t, was gleich an-1 ist.
Nach Fermat muss für eine Primzahl gelten: an-1 &isequiv; 1 (mod n). Somit muss das letzte Glied der Folge eine 1 sein. Für den Vorgänger v des letzten Glieds muss also gelten: v2 = 1 (mod n) ⇔ v2 – 1 = 0 (mod n).
⇒ n|v2 – 1 ⇔ n|(v – 1)(v + 1)
⇒ n|(v – 1) oder n|(v + 1) ⇔ v – 1 = 0 (mod n) oder v + 1 = 0 (mod n)
⇒ v = 1 (mod n) oder v = -1 (mod n)
Folglich ergeben sich zwei Möglichkeiten wie eine Folge aussehen kann: Entweder enthält sie lauter Einsen oder sie enthält irgendwann (spätestens als vorletztes Glied) eine -1 und nachfolgend nur Einsen.
Ergibt sich für das zu testende n solch eine Folge, so ist n wahrscheinlich prim. Lediglich starke Pseudoprimzahlen können noch auftreten. Wählt man nun für die Basis a verschiedene Werte, so kann das Auftreten von starken Pseudoprimzahlen erheblich minimiert werden. So ist die Wahrscheinlichkeit des Auftretens einer Pseudoprimzahl nach vier verschiedenen Basen kleiner als 0.4%.
Primzahltest nach Pratt
Der Primzahltest nach Pratt ist ein deterministischer Primzahltest, d.h. die Primalität einer Zahl kann zu 100% gesichert werden. Das Verfahren verwendet das Lehmer Theorem, welches auf dem kleinen Fermatschen Satz aufbaut:
an – 1 ≡ 1 (mod n) für a ∈ [2,n – 1]
Für alle Primfaktoren q von n – 1 gilt: a(n – 1)/q ist NICHT ≡ 1 (mod n)
Bisher ist noch kein Algorithmus bekannt, der zu einer Zahl alle Primfaktoren in polynomieller Laufzeit ermittelt. Der Algorithmus von Pratt stellt sog. Zertifikate aus, welche bezeugen, dass eine Zahl eine Primzahl ist. Dies geschieht für alle Primfaktoren von n – 1.Ein Zertifikat ist rekursiv definiert wie folgt:
Z (2) = (1)
Z (n) = (a), falls n – 1 prim ist
Z (n) =(a; q1, Z(q1); q2, Z(q2) ;…; qn, Z(qn); )
Für Z=37 ergibt sich folgendes Zertifikat:
Z (37) =(3; 3, (2; 2, (1)); 3, (2; 2, (1)); 2, (1); 2, (1) 😉
Dieses wird verifiziert:
| Für n: | Für alle q von n – 1 (außer q = 2, da Z(2) = 1 ): |
| 337-1 ≡ (mod 37) | 23-1≡ (mod 3) |
| 330/2 ≡ (mod 37) | 22/2 ≡ (mod 3) |
| 330/3 ≡ (mod 37) | Jedes innere Zertifikat wird wie hier gezeigt verifiziert |
Damit ist 37 eine Primzahl.
Der Beweis dieses Verfahrens befindet sich in http://www4.informatik.tu-muenchen.de/lehre/vorlesungen/perlen/SS09/Unterlagen/Pratt.pdf (20.10.2009)
AKS Primzahltest
Dieser Primzahltest wurde 2002 von den Indischen Akademikern Manindra Agrawal, Neeraj Kayal, Nitin Saxena des Indian Institue of Technology Kanpur entwickelt. Dieser Primzahltest ist vor allem für die Komplexitätstheorie interessant, da er ein polynomielles Zeitverhalten hat und somit zeigt, dass das Problem Primzahltest in P liegt, was bis dahin nicht geklärt war. Dieser Primzahltest arbeitet nach folgendem Algorithmus:
Hierbei steht die Ausgabe COMPOSITE für zusammengesetzte Zahl und die Ausgabe PRIME für Primzahl.
In Zeile zwei wird die kleinste Ordnung von n gesucht. Die Ordnung eines Gruppenelementes einer Gruppe G ist die kleinste natürliche Zahl n > 0, für die gilt: gn = e, wobei e das neutrale Element der Gruppe ist.
In Zeile 5 wird die Eulersche-Phi-Funktion verwendet. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen a ≤ n zu ihr teilerfremd sind.
Der Beweis des Verfahrens basiert auf dem Vergleich von Polynomen mit dem einem Konstruierten Restklassenring von R. Nähere Informationen hierfür sind im Scientific Paper Primes is in P unter http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf zu finden
Quellen
1. http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
2. http://de.wikipedia.org/wiki/Fermatscher_Primzahltest
4. http://de.wikipedia.org/wiki/Miller-Rabin-Test
6. http://www2-fs.informatik.uni-tuebingen.de/~reinhard/krypto/Pratt/Pratt_Applet_d.html
8. http://www2-fs.informatik.uni-tuebingen.de/~reinhard/krypto/AKSTest/AKSdeu.html
Alle hier gelisteten Quellen wurden zuletzt am 20.10.2009 aufgerufen
Abb. 1 Auszug aus dem Scientific Paper Primes is in P von Agrawal, Kayal und Saxena: Der AKS-Algorithmus
Autor des Beitrags
Stefan Münch
