praktische Relevanz des fermat'schen Primzahltests
-
Hallo liebe Programmierfreunde,
Ich habe im Netz Funkionen gefunden, die den fermatschen Primzahltest zeigen und daraus mal eine lauffähige main in c++ gebaut und das Programm analysiert.
Hier der Quelltext:#include<iostream> #include<cmath> //#include<ctime> //#include<cstdlib> using namespace std; unsigned long long upower(unsigned int, unsigned int); void prime(); int main(){ prime(); return 0; } unsigned long long upower(unsigned i, unsigned N) { unsigned long long power = 1; if (i <= 1) return i; while (N-- > 0) { unsigned long long power_before = power; power *= i; if (power < power_before) {cout<<"------>Overflow/Überlauf<--------\n"; return 0;} } return power; } void prime() { unsigned i, N; cout<<"Geben Sie bitte eine zu testende Primzahl ein:"; cin>>N; for (i = 2; i < N; i++) { if ((upower(i, N - 1) % N) != 1) {cout<<"Zahl nicht prim / bzw. bei Überlauf -moeglicherweise- nicht prim"<<endl; return;} //beachte: return wird hier zum reinen Verlassen der Funktion an der jeweiligen Stelle benutzt //also zum Abbrechen ohne Wertrückgabe, da die Funktion auf void geschaltet ist. } cout<<"Zahl ist prim"<<endl; return; } /************************************************************************ Der fermatsche Primzahltest beruht auf dem kleinen fermatschen Satz: Für jede Primzahl p und jede dazu teilerfremde natürliche Zahl a ist folgende Kongruenz erfüllt: ****************************************************************** ************************a^(p-1) = 1 mod p ******************** ****************************************************************** Das Programm hier überprüft dies direkt und einfach, indem es die Bedingung direkt auf das Ergebnis hin testet ---> nämlich ob a hoch p-1 eben den Rest 1 hat und dies mehrmals. ************************************************************************/ /*********************************************************************** Die Funktion upower überprüft nur ob kein Überlauf stattfindet, der Test findet in der Funktion prime(); statt ************************************************************************/
Ich habe nur eine praktische Verständnisfrage diesbezüglich: die for Schleife
in der Funktion prime() tut dies bis zu der Grenze von N selbst testen.
Ich glaube aber, dass dies in der Praxis bei großen Zahlen kaum Sinn machen
sollte : 1.) wäre der Rechenaufwand viel zu hoch - geht nicht ! ? 2.) Wenn man
den Test mehrmals durchführt, für unterschiedliche Basen , sollte die Wahrscheinlichkeit, dass die getestete Zahl eine Primzahl ist, doch ziemlich sicher sein ? z.b. 20 mal getestet ?
-
Es gibt Zahlen für die dieser Test kategorisch nicht funktionieren kann - nämlich Carmichael-Zahlen.
Eulers Totient-Theorem ist eben einfach eine notwendige, nicht aber eine hinreichende Bedingung.Solltest du probabilistische Primzahl-Tests suchen, wärst du mit Miller-Rabin gut bedient: Ist praktisch sehr relevant und einfach zu implemtentieren.
-
softpad schrieb:
Ich habe nur eine praktische Verständnisfrage diesbezüglich: die for Schleife
in der Funktion prime() tut dies bis zu der Grenze von N selbst testen.Das ist sehr ungewöhnlich, bis ganz hoch zu N zu gehen.
Ich glaube aber, dass dies in der Praxis bei großen Zahlen kaum Sinn machen
sollte : 1.) wäre der Rechenaufwand viel zu hoch - geht nicht !Wenn du wirklich alle möglichen Basen ausprobierst, dann ja.
? 2.) Wenn man
den Test mehrmals durchführt, für unterschiedliche Basen , sollte die Wahrscheinlichkeit, dass die getestete Zahl eine Primzahl ist, doch ziemlich sicher sein ? z.b. 20 mal getestet ?So ist es.
Alle diese Dinge stehen in jeder Beschreibung des fermatschen Primzahltests.
PS: Hör auf zu plenken, das aktiviert bei mir immer den Trollalarm.
-
SeppJ schrieb:
PS: Hör auf zu plenken, das aktiviert bei mir immer den Trollalarm.
Vielleicht ist er Franzose.
-
softpad schrieb:
Ich habe nur eine praktische Verständnisfrage diesbezüglich: die for Schleife in der Funktion prime() tut dies bis zu der Grenze von N selbst testen. Ich glaube aber, dass dies in der Praxis bei großen Zahlen kaum Sinn machen sollte : 1.) wäre der Rechenaufwand viel zu hoch - geht nicht ! ?
So ist es. N Divisionen sollten viel billiger sein als N (modulare!) Potenzierungen.
Was man immer machen kann, ist vor einen normalen Primzahlentest einen kleinen Fermat-Check mit Basis 2 vorzuschalten. Wenn der Nichtprimalität anzeigt, kann man sich den ausführlichen Test sparen.
softpad schrieb:
2.) Wenn man den Test mehrmals durchführt, für unterschiedliche Basen , sollte die Wahrscheinlichkeit, dass die getestete Zahl eine Primzahl ist, doch ziemlich sicher sein ? z.b. 20 mal getestet ?
Leider nein. Es gibt wie schon genannt die bösen Carmichael-Zahlen.
Aber was Du machen kannst, ist sowas:
if(!isSPRP(p,7252)) return false;//die 7252 deckt ab hier den größten Bereich Fehlerfrei ab if(p<13747) return true;//bis p<13747 ist das Ergebnis sicher if(!isSPRP(p,1607438)) return false;//die 1607438 deckt ab hier den größten Bereich Fehlerfrei ab if(p<45559729) return true;//bis p<45559729 ist das Ergebnis sicher if(!isSPRP(p,9786)) return false;//die 9786 deckt den Rest bis 2^32 ab return true;
https://www.c-plusplus.net/forum/99688-full
Wobei ich da SPRP statt nur PRP verwendet habe, ist stärker und schneller.
Und mit SPRP haste (falls wie alle vermuten die GRH gilt) noch ne Garantie: Brauchst nur bis log(N)² zu testen.
http://en.wikipedia.org/wiki/Miller–Rabin_primality_test#Deterministic_variants_of_the_test
-
Danke!