Primzahlen interessieren Mathematiker und ganz besonders Zahlentheoretiker überall auf der Welt schon seit langer Zeit: Euklid's Beweis der Unendlichkeit der Primzahlmenge z.B. ist uns allen bekannt und gilt als das typische Beispiel eines indirekten Beweises. Primzahl-Eigenschaften wurden lange erforscht und inzwischen kommt ihnen auch ein enormer praktischer Nutzen bei der schwer zu knackenden Verschlüsselung RSA zu. RSA verwendet zwei (heutzutage etwa 1024 oder 2048 Bit lange) Primzahlen, um mit ihnen Daten zu verschlüsseln. Doch zu zeigen, dass die verwendeten Primzahlen wirklich welche sind, war bis vor kurzem (vor Erfindung des AKS-Algorithmus') eine schwierige bzw. unangenehm langsame Angelegenheit. Deshalb verwendete man (und verwendet aus Performancegründen auch jetzt noch) so genannte Starke Pseusoprimzahlen anstelle von "echten" Primzahlen.
Eine Zahl n heißt Pseudoprimzahl zur Basis a, wenn sie den kleinen Satz von Fermat mit a (ggT(a,n)=1) erfüllt: \lr(1.1.1)a^(n-1)==1 (mod n)
Eine ungerade Zahl n heißt starke Pseudoprimzahl zu Basis a, wenn sie eines dieser zwei Kriterien erfüllt: Sei n-1=2^s*r (mit r==1 (mod 2)) Dann gilt für starke Pseudoprimzahlen entweder: \lr(1.1.2)a^r==1 (mod n) oder \lr(1.1.3)a^(2^t*r)==-1(mod n) mit 0<=t Jede Starke Pseudoprimzahl ist gleichzeitig auch Pseudoprimzahl zur selben Basis.
Anmerkung: Oft werden nur die zusammengesetzten Zahlen, die diese Kriterien erfüllen als (stark) pseudoprim bezeichnet. Eine beliebige Zahl, die die Kriterien erfüllt wird in solchen Fällen als "wahrscheinliche Primzahl" (Probable Prime Number) bezeichnet. Beide Namensgebungen sind üblich. Man sollte immer drauf achten, was im konkreten Fall gemeint ist.
1.2 Beispiele
Beide Kriterien sind notwendig, aber nicht hinreichend für Primalität. Das heißt insbesondere, dass eine Zahl, die eines dieser beiden Kriterien nicht erfüllt, ganz sicher zusammengesetzt also nicht prim ist. Beispiel 49:
a=2,n=49 Eingesetzt in \ref(1.1.1): 2^48==2^(16*3)==23^3==15!==1 (mod 49) => 49 ist zusammengesetzt
Es kann allerdings Zahlen geben, die die Kriterien bestehen, obwohl sie zusammengesetzt sind. Beispiel 561=3*11*17 (die erste Carmicheal-Zahl):
a=2,n=561 => s=4,r=35 Eingesetzt in \ref(1.1.1): 2^560==1 (mod 561) => 561 ist Pseudoprim zu Basis 2. Eingesetzt in \ref(1.1.2): 2^r==2^35==263!==1 (mod 561) Eingesetzt in \ref(1.1.3): t=0 => 2^1r==2^35==263!==-1 (mod 561) t=1 => 2^2r==263^2==166!==-1 (mod 561) t=2 => 2^4r==166^2==67!==-1 (mod 561) t=3 => 2^8r==67^2==1!==-1 (mod 561) => Kriterien \ref(1.1.2) und \ref(1.1.3) nicht erfüllt => 561 ist zusammengesetzt.
Es kann sogar Zahlen geben, die beide Kriterien erfüllen. Beispiel 2047=23*89:
a=2,n=2047 => s=1,r=1023 Eingesetzt in \ref(1.1.1): 2^2046==1 (mod 2047) => 2047 ist Pseudoprim zur Basis 2. Eingesetzt in \ref(1.1.2): 2^1023==1 (mod 2047) => 2047 ist stark Pseudoprim zur Basis 2.
Jede echte Primzahl erfüllt immer beide Kriterien. Allerdings gibt es auch zusammengesetzte Zahlen, die diese Tests bestehen. Für den kleinen Fermat sind das z.B. die Carmichael-Zahlen, die diesen Test für alle a kleiner als n bestehen. Für den zweiten Test gibt es sowas spezielles scheinbar nicht: Eine Zahl, für die etwas analoges gilt, ist nicht bekannt und, wenn die erweiterte Riemannhypothese korrekt ist, besteht auch keine zusammengesetzte Zahl diesen Test für sämtliche a kleiner als 70*ln(n)2. Indem man mehrere Basen a testet, kann man die Wahrscheinlichkeit, dass man eine zusammengesetzte Zahl fälscherweise als Prim deklariert, soweit senken, dass sie unterhalb der Fehlerwahrscheinlichkeit der Hardware liegt.
1.3 RSA als praktisches Beispiel für den Einsatz von Pseudoprimzahlen
Nach dem Satz von Euler-Fermat gilt: \forall a (ggT(a,n)=1) : a^\phi(n)=1 (mod n) Wobei \phi(n) die Euler-Totient-Funktion ist.
Wenn n=pq gilt mit p,q \el \IP und p!=q, dann gilt \phi(n)=(p-1)(q-1). Seien nun e,d zwei Zahlen mit ed=1 (mod \phi(n)), d.h. es gibt ein k \el \IZ mit ed=k\phi(n)+1.
Jetzt kann man eine Nachricht m sehr einfach verschlüsseln, indem man c==m^e (mod n) berechnet. Das Entschlüsseln erfolgt dann über m==c^d==(m^e)^d==m^(k\phi(n)+1)==m*(m^\phi(n))^k==m*1^k==m (mod n).
Da man zwei Schlüssel e und d hat, handelt es sich hier um ein so genanntes asymmetrisches Verschlüsselungs-Verfahren. In der Regel wird einer dieser Schlüssel veröffentlicht (Public-Key) und einer geheim gehalten (Private Key), so dass jeder eine Nachricht für den Besitzer des privaten Schlüssels verschlüsseln, aber nur dieser eine solche Nachricht entschlüsseln kann. p und q werden in der Praxis dadurch erzeugt, dass man zufallsgesteuert solange ungerade Zahlen der gewünschten Länge erzeugt, bis diese einen Pseudoprimzahl-Test bestehen. In der Regel ist das ein Miller-Rabin-Test (das ist ein anderer Name für den Test, der auf diesem Kriterium basiert), der für die gegebene Zahl n überprüft, ob sie eine starke Pseudoprimzahl zu 10-20 verschiedenen zufällig gewählten Basen ist.
2. Herleitung des Kriteriums für Starke Pseudoprimzahlen
Die obige Defintion einer starken Pseudoprimzahl (siehe ref(1.1)) folgt eigentlich direkt aus dem kleinen Fermat:
a^(n-1)==1 (mod n) <=> a^(n-1)-1==0 (mod n)
Da n ungerade ist, kann man n-1 als 2b darstellen.
a^2b-1==(a^b-1)(a^b+1)==0 (mod n)
Wobei nicht beide Faktoren gleich 0 sein können, denn sonst würde die Differenz (a^b+1)-(a^b-1)=2 von n geteilt werden, was ein Widerspruch zu n ungerade ist. Der erste Faktor kann nach dem selben Prinzip aufgespalten werden, wenn b gerade ist, so dass man am Ende eine Aufspaltung in dieser Form erhält: a^(n-1)-1==(a^r-1)(a^r+1)(a^2r+1)(a^4r+1)...(a^(2^(s-1)*r)+1)==0 (mod n) mit r==1 (mod 2)
Hier wird der erste Faktor 0, wenn a^r==1 (mod n) gilt. Die andern werden 0, wenn a^(2^t*r)==-1 (mod n) gilt mit 0<=t
Mit diesem Kriterium können wir recht genau überprüfen, ob eine Zahl prim ist, denn die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl diesen Test für x zufällig gewählte Basen übersteht ist maximal 4^(-x). Meistens werden für x Werte von 10-20 verwendet, da damit die Wahrscheinlichkeit eine Falscheinschätzung unter der eines Fehlers in der Berechnung durch Hardwaredefekte fällt. Manchmal wird zusätzlich noch ein Lucas-Pseudoprimzahl-Test durchgeführt, um die Wahrscheinlichkeit noch weiter zu senken. Ein von Carl Pomerance vorgeschlagener Test, bestehend aus einem Miller-Rabin-Test mit bis zu 27 verschiedenen Basen und einem Lucas-Pseudoprimzahl-Test, ist so gut, dass bis heute keine zusammengesetzte Zahl bekannt geworden ist, die den Test bestehen würde. (Das könnte allerdings auch an der vergleichsweise niedrigen Belohnung von $620 liegen ;-) )
Ein Algorithmus zur Anwendung des Kriteriums für starke Pseudoprimzahlen
\sourceon Eingabe: n: die zu prüfende Zahl, w: Anzahl der Basen (beide aus IN) Ausgabe: PSEUDOPRIM oder NICHTPRIM
(1) Ausschluss trivialer Fälle (1.1) Überprüfe ob (n mod 2)=0 gilt. Wenn nein gib für n=2 (PSEUDO)PRIM aus, sonst NICHTPRIM. (1.2) Wenn n=1 gib NICHTPRIM aus. (2) Zerlegung n-1=2^s*r (2.1) Setze r=(n-1)/2 und s=1 (2.2) Solange (r mod 2)=0 wiederhole: (2.2.1) Setze r=r/2 (2.2.2) Setze s=s+1 (3) Hauptschleife (3.1) setze i=0 (3.2) solange i (3.2.1) wähle a zufällig aus [2;n-1] (3.2.2) Wenn ggT(a,n)!=1 gib NICHTPRIM aus (3.2.3) setze x=a^r mod n (3.2.4) Überprüfe ob abs(x)=1 gilt. Wenn ja, setze i=i+1 und gehe zurück zu (3.2) (3.2.5) setze composite=t=1 (3.2.6) Solange t (3.2.6.1) setze x=x^2 mod n (3.2.6.2) Wenn x=-1 gilt, setze composite=0 und beende Schleife (3.2.6) (3.2.6.3) Setze t=t+1 und gehe zu (3.2.6) (3.2.7) Wenn composite=1 gilt, gib NICHTPRIM aus (3.2.8) Setze i=i+1 und gehe zu (3.2) (4) Gib PSEUDOPRIM aus. \sourceoff
In der Praxis kann man das ganze noch verbessern, indem man z.B. den Schritt (2.2.1) durch eine Bitverschiebung ersetzt, oder indem man die Operation mod 2 durch eine bitweise Und-Verknüpfung mit 1 realisiert. Insgesamt kann man sagen, dass dieser Algorithmus sehr schnell ist. Für die Überprüfung einer Basis werden (1+O(1))*log2n Multiplkationen mod n benötigt.
Ausblick
Wie gesagt, gilt unter der Bedingung, dass die erweiterte Riemann-Hypothese korrekt ist, dass für jede Zusammengesetzte Zahl n mindestens eine Basis a < 70*ln(n)^2 existiert, für die n den Miller-Rabin-Test nicht besteht. Wenn also die Hypothese bewiesen werden kann (was wohl scheinbar nur eine Frage der Zeit ist), dann kann man aus dem bisher probalistischen Primzahltest einen deterministischen Test machen, der auch noch sehr effektiv wäre.
Ich hoffe, dass ich euch einen verständlichen Überblick über die starken Pseudoprimzahlen, ihre Anwendung und ihren Nachweis gegeben habe. Neben den starken Pseudoprimzahlen gibt es weitere Kriterien und nach ihnen benannte Pseudoprimzahlen. Unter diesen Euler-Jacobi-, Lucas-, Starke Lucas-, Extra Starke Lucas-, Frobenius- und viele weitere Pseudoprimzahlen. Auch mit diesen kann man Pseudoprimzahl-Tests implementieren, die in der Praxis aber seltener verwendet werden, da sie oft langsamer sind als der hier vorgestellte Algorithmus.
Müßte bei (3.2.4) nicht die Schleife beendet und "PSEUDOPRIM" ausgegeben werden, wenn abs(x)=1 gilt, oder habe ich was falsch verstanden?
Ansonsten aber super Artikel!
@plex:
Im Prinzip schon, aber da mehrere Basen getestet werden sollen mit diesem Algorithmus, steht an dieser Stelle nur fest, dass die eingebene Zahl stark Pseudoprim zu der aktuellen Basis ist. Deshalb wird das i erhöht und dann die Schleife fortgesetzt um so die nächste Basis auch zu prüfen.
endlich eine gute, praktische Anleitung für einen Primzahlentest, mit den Hintergründen.
Oft ist die auch die Rede davon, dass nach einem Wahrscheinlichkeitstest eine sichere Methode eine Primzahl überprüft habe. Wie ein sicheres Verfahren aussieht, habe ich neulich im Internet gefunden: .
Die Methode, bzw. der Beweis ist relativ neu (August 2002).
jetzt hab ichs gesehen, am Anfang deines Artikels. Vielleicht nimmt sich ein Planetarier die Mühe den AKS Test "auszudeutschen".
Wie effizient (Rechenzeit) sind eigentlich exakte Tests gegenüber stochastischen?
Effizienz ist immer so eine Sache... Das kann man schwer sagen in einigen Fällen. Ich kann dir aber ein paar grundlegende Abschätzungen geben:
Der AKS-Test (der wie du sagst exakt ist) ist in der Komplexitätsklasse O(log^(6+\epsilon) n) wobei n die Länge\/Stellenanzahl der zu testenden Zahl ist.
Es gibt einen andern Test von Cohen, Lenstra und zwei weiteren Mathematikern, deren Namen mir gerade entfallen sind, dessen Laufzeit O(log^(log log log n) n) ist. Dieser Test ist auch deterministisch, also exakt.
Andere Tests, zum Beispiel der hier vorgestellte Test, sind probalistisch (das heißt sie erzeugen nur wahrscheinlich richtige Ergebnisse) aber oft schneller. Der Miller-Rabin-Test den ich hier vorgestellt habe ist meines Wissens der, der das beste Verhältnis von Genauigkeit und Geschwindigkeit hat.
\(\begingroup\)Den vorletzten Umforungsschritt unter Punkt 1.3 schaffe ich nicht nachzuvollziehen. Könnte mir jemand helfen ihn zu verstehen?\(\endgroup\)
Du meinst diese Zeile hier?
\blue\ m==c^d==(m^e)^d==m^(k\phi(n)+1)==m*(m^\phi(n))^k==m*1^k==m (mod n)
Wir haben c vorher als m^e festgelegt. Der erste Schritt ist also nur ein Einsetzen.
m==m^(e*d) (mod m)
Dann wenden wir das Potenzgesetz (a^b)^c=a^(b*c) an und die Tatsache, dass e und d so gewählt wurden, dass e*d=k*\phi(n)+1 ist.
Dann wenden wir das obige und sowie Potenzgesetz a^b*a^c=a^(b+c) an:
m^(e*d)==m^(k\phi(n))*m==(m^\phi(n))^k*m (mod m)
Und da laut dem Satz von Euler m^\phi(n)==1 (mod m) ist, ist gilt c^d==1^k*m==m (mod m)
\(\begingroup\)RSA is von Rivest, Shamir und Adleman, und der ARCL primality test ist von Cohen und Lenstra, optimiert wurde er von Adleman und Rumely (wenn ich mich nich irre), könnte auch Rivest gewesen sein. Deshalb ARCL, der exakt ist, aber etwas aufwendig. Miller-Rabin hat ein besseres Preis- (Rechenaufwand)-Leistungs-Verhältnis. Sonst 'n hübscher Artikel über Pseudoprimzahlen!
verspäteter Gruß, der Zahlenbüffel.\(\endgroup\)
\(\begingroup\)@Roland:
Bezüglich welcher Basis? Meines Wissens ist bisher keine nicht-prime Zahl, die stark pseudoprim zu allen kleineren Basen ist, bekannt geworden. (Und mit Hilfe der verallgemeinerten Riemann'schen Hypothese kann man zeigen, dass es sowas auch nicht geben kann)
Ansonsten schreibe dir doch ein kleines Programm, um z.B. die starken Pseudoprimzahlen zur Basis 2 zu finden. Unterhalb von 1.000.000 gibt es schon 46 nicht-Primzahlen, die stark pseudoprim zur Basis 2 sind, du wirst also sehr schnell fündig werden.
mfg Gockel.\(\endgroup\)
\(\begingroup\)Hi!
Wollte mich interessehalber mal in das Thema einlesen, doch leider habe ich schon eine Frage im ersten Beispiel. Dort heisst es:
\
2^48==2^(16*3)==23^3==15!==1 (mod 49)
Wie geht dieses kürzen? Gibt es zu der Gauss-Kongruenz (ist es doch, oder?) eine gute Erläuterung auf dem matheplanet?
Schon mal vielen Dank im Vorraus
Felix\(\endgroup\)
\(\begingroup\)Hi.
Es gilt für die Zweier-Potenzen mod 49:
2^5==32==-17
2^6==-34==13
2^7==26
...
Und schließlich eben 2^16==23. Ich habe in der Gleichung nichts weiter getan, als eben 2^16 durch 23 ersetzt.
Oder meinst du etwas anderes? \(Was ist z.B. eine Gauß-Kongruenz?\)
mfg Gockel.\(\endgroup\)
\(\begingroup\)Hallo Gockel,
war genau das was ich meinte.
Vielen Dank für die prompte Antwort.
Gruss
Felix
P.S.
mit der Gauss-Kongruenz meinte ich genau diese Schreibweise
siehe auch Gauss-Kongruenz (Wikipedia)
\
a==b mod n
Hab eben nur nicht genau genug hingeguckt\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
