Primzahltest



  • Hallo,

    mit welchen Methoden testet ihr, ob eine Zahl (große Zahl) eine Primzahl ist?

    Rabin-Miller?

    ...?



  • wie groß?



  • Mich würde ein schneller Primzahltest interessieren, für Primzahlen > 2^25 < 2^32.

    Edit: Schnell=Nicht den PC den ganzen Tag laufen lassen o.ä.



  • Brutus schrieb:

    Mich würde ein schneller Primzahltest interessieren, für Primzahlen > 2^25 < 2^32.
    Edit: Schnell=Nicht den PC den ganzen Tag laufen lassen o.ä.

    da bin ich ganz zufrieden mit

    inline bool isPrimeCheckBelow6(u32 p)
    {//bei p<=6 einfach nachschauen. 
            //Das Bitmuster ersetzt ein ArrayOfBool.
            return getBit(0x002c,p);//Nur die Bits 2,3,5 sind gesetzt.
    };
    inline bool isPrimeCheckFactorsBelow6(u32 p)
    {//Teiler 2,3 und 5 mit einer Division testen
            return getBit(0x208A2882,p%30);//Nur die Bits 1,7,11... sind gesetzt.
    };
    
    //Zitat: "Rather than divide by just the primes, it is sometimes 
    //more practical to divide by 2, 3 and 5; then by all the numbers 
    //congruent to 1, 7, 11, 13, 17, 19, 23, and 29 modulo 30--again 
    //stopping when you reach the square root. This type of factorization 
    //is sometimes called wheel factorization. Look in most any elementary 
    //text on number theory for information about these tests. 
    //Quelle: http://www.utm.edu/research/primes/prove/prove2.html
    
    //Die Idee, daß Primzahlen-Kandidaten p nur dann überhaupt als 
    //Prizahlen in Frage kommen, wenn p mod 30 nicht durch 2,3,5 
    //teilbar ist, wird in den folgenden Verfahren öfters zur Anwendung 
    //kommen. Bitte behalten Sie diesen Satz stehts im Gedächtnis!
    
    //Offset zur nächstmöglichen Primzahlenposition
    u32 diffPrime[30]={1,6,5,4,3,2,1,4,3,2,1,2,1,4,3,2,1,2,1,4,3,2,1,6,5,4,3,2,1,2};
    //Selber Offset zyklisch in Z30 erspart: if(m>30)m-=30
    //Zweck: Sprünge sind auf modernen Prozessoren zu teuer.
    u32 diffPrimeM[30]={1,6,5,4,3,2,1,4,3,2,1,2,1,4,3,2,1,2,1,4,3,2,1,6,5,4,3,2,1,2-30};
    
    bool isPrimeCheckFactorsAbove5ByWheelFactorisation(u32 p)
    {
            u32 t=7;
            u32 mt=7;
            while(p%t!=0)
            {
                    if(t*t>p) return true;
                    t+=diffPrime[mt];
                    mt+=diffPrimeM[mt];
            };
            return false;
    };
    
    u32 powMod(u32 base,u32 exp,u32 modul)
    {//rechnet 'base hoch exp mod modul'
            u32 a1=base,z1=exp,x=1,m=modul;
            while(z1!=0)
            {
                    while((z1%2)==0)
                    {
                            z1/=2;
                            a1=mulMod(a1,a1,m);
                    };
                    --z1;
                    x=mulMod(x,a1,m);
            };
            return x;
    };
    
    bool isSPRP(u32 n,u32 a)
    {
    // Zitat: "One way to make the Fermat probable primality test more 
    //      accurate is to write n-1=2sd where d is odd and s is nonnegative. 
    //      Then n is a strong probable-prime base a (an a-SPRP) if either 
    //      ad = 1 (mod n) or (ad)2r = -1 (mod n) for some nonnegative r 
    //      less than s."
    //      Quelle: http://www.utm.edu/research/primes/glossary/StrongPRP.html 
    //      
    //      Zitat: "Millers Test: Assume the generalized Riemann hypothesis 
    //      is true. If n is an a-SPRP for all integers a with 
    //      1 < a < 2(log n)2, then n is prime.
    //      Quelle: http://www.utm.edu/research/primes/glossary/MillersTest.html
            u32 o=n-1;
            u32 e=findFirstBitTrue(o);
            o>>=e;
            u32 x=powMod(a,o,n);
            if(x==1) return true;
            if(x==n-1) return true;
            for(u32 i=0;i<e;++i)
            {
                    x=mulMod(x,x,n);
                    if(x==n-1) return true;
            };
            return false;
    };
    
    bool isPrimeCheckFactorsAbove5BySPRPCheck(u32 p)
    {
    //Copyright Volkard Henkel <volkard@normannia.de>
    // If n < 4,759,123,141 is a 2, 7, and 61-SPRP, then n is prime.
    //      Quelle: http://www.utm.edu/research/primes/glossary/StrongPRP.html
    //
    //      Diese drei Tests reichen also, um alle Zahlen im Bereich bis 
    //      2^32 zu testen. Besser sind die folgenden Zahlen, weil bis 
    //      n<45559729 nur zwei Tests benötigt werden. 
    //      Die Zahlen habe ich mit einem eigens dafür geschriebenen Programm 
    //      gesucht. 
            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;
    };
    
    //Position der nächsten Primzahl
    u32 firstPrimeNext[11]={2,2,3,5,5,7,7,11,11,11,11};
    
    u32 nextPrime(u32 last)
    {
            if(last<11)
                    return firstPrimeNext[last];
            else if(last<1000)//TODO: gute Grenze finden!
            {
                    u32 p=last;
                    u32 mp=p%30;
                    do
                    {
                            p+=diffPrime[mp];
                            mp+=diffPrimeM[mp];
                    }while(!isPrimeCheckFactorsAbove5ByWheelFactorisation(p));
                    return p;
            }
            else
            {
                    u32 p=last;
                    u32 mp=p%30;
                    do
                    {
                            p+=diffPrime[mp];
                            mp+=diffPrimeM[mp];
                    }while(!isPrimeCheckFactorsAbove5BySPRPCheck(p));
                    return p;
            };
    };
    
    inline bool isPrime(u32 p)
    {
            if(p<6) return isPrimeCheckBelow6(p);
            if(!isPrimeCheckFactorsBelow6(p)) return false;
            if(p<49) return true;
            //TODO: gute Grenze finden!
            if(p<1000) return isPrimeCheckFactorsAbove5ByWheelFactorisation(p);
            return isPrimeCheckFactorsAbove5BySPRPCheck(p);
    };
    

    die verwendeten funktionen mulMod und getBit hab ich gerade nicht verfügbar. kann ich aber noch besorgen, wenn du sie nicht hinkriegst.

    zur zeit arbeite ich daran, die drei SPRP-Tests zu einem zu machen und die obergrenze ein wenig über 2^32 zu bringen. mal schauen, wie es sich entwickelt.



  • hmm... Mindestlänge dreistellig bis unbegrenzt.
    Mich würde es interessieren, wie man mit Papier und Bleistift das löst.
    Also ohne PC, Mathematica etc.



  • tip? schrieb:

    hmm... Mindestlänge dreistellig bis unbegrenzt.
    Mich würde es interessieren, wie man mit Papier und Bleistift das löst.
    Also ohne PC, Mathematica etc.

    per hand?! uff.
    die primzahlen bis zur wurzel der zahl abchecken, ob sie ein teiler der zahl sind.

    beispiel:
    zahl=4711

    teiler 2 klappt nicht (wegen endziffer)
    teiler 3 klappt nicht (wegen quersumme)
    teiler 5 klappt nicht (wegen endziffer).

    teiler 7...
    ich addiere und subtrahiere so lange offensichtlich durch 7 teilbare zahlen, bis ich sicher bin.
    4711+210
    4921-4900
    21 ist durch 7 teilbar.

    ups, 4711 war keine primzahl.

    ich schau mal 4709 an.

    teiler 2 klappt nicht (wegen endziffer)
    teiler 3 klappt nicht (wegen quersumme)
    teiler 5 klappt nicht (wegen endziffer).
    teiler 7 klappt nicht (weil 4711 klappt (ich gedächtnis hab)).

    teiler 11...
    4709-4400
    309+22
    331-330
    1
    klapt nicht

    teiler 13...
    4709-3900
    809+520
    1329
    klappt nicht

    teiler 17...
    naja, und so müßte ich weitermachen bis zum teiler 67, weil das die abgerundete wurzel von 4709 ist. mühsam, aber es geht.

    ich denke, miller rabin etc sind recht gemein per hand anzuwenden. allenfalls noch die methode von äh, war's fermat oder euler? die, wo man versucht, die zahl als differenz von zwei quadratzahlen darzustellen. braucht aber durchschnittlich noch viel länger bei zusammengesetzten zahlen.



  • hmm.. gibt es da echt keinen Trick?

    Mit Fermat oder Euler geht es auch, aber da muss man auch erstmal die
    Eulersche - Phi - Funktion berechnen. Was auch ziemlich lange dauert, wenn die Zahl entsprechend groß ist.

    Schade, dass hier kein Mathegenie ist 🙂

    Aber danke für deine Antwort.



  • tip? schrieb:

    Mit Fermat oder Euler geht es auch, aber da muss man auch erstmal die
    Eulersche - Phi - Funktion berechnen. Was auch ziemlich lange dauert, wenn die Zahl entsprechend groß ist.

    sowas meinte ich nicht. ich meinte schon http://mathworld.wolfram.com/FermatsFactorizationMethod.html
    ist halt relativ einfach zu rechnen, so ohne divisionen und so. aber hat halt das fette problem, daß bei zusammengesetzten ahlen sozusagen zuerst die großen teiler und am end erst die kleinen getestet werden.
    das von mir vorgestellte verfahren testet zuerst die kleinen, da fliegen schon 50% der zahlen raus, weil sie gerade sind, davon nochmal 33% weil sie durch 3 teilbar sind, davon noch 20%, weil sie durch 5 teilbar sind...

    Schade, dass hier kein Mathegenie ist 🙂

    die sind schon hier, aber sie warten auf das, was sie "sehr interessante fragen" nennen.

    du wirst keine geschlossene formel finden und auch kein verfahren, das einfach auf papier zu rechnen ist.

    edit: habe es eben mal mit PRP per hand probiert. ist unheimlich mühsam. aber bei zehnstelligen zahlen wird's vermutlich doch noch einfacher sein als alle teiler zu testen.



  • tip? schrieb:

    hmm.. gibt es da echt keinen Trick?

    da gibts nen primzahltest von mir: http://www.c-plusplus.net/forum/viewtopic.php?t=98124&start=0
    der trick besteht bei riesengroßen zahlen eigentlich darin welche zu suchen die mit hoher wahrscheinlichkeit primzahlen sind 🙄 .
    eine magische formel die sofort sagt ob eine zahl prim ist oder nicht, gibt es nicht.


Anmelden zum Antworten