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 ?


  • Mod

    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.


  • Mod

    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.


  • Mod

    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!


Log in to reply