V
fall meine einen interessiert:
inline bool isPrimeCheckBelow32(u32 p)
{//bei p<=6 einfach nachschauen.
//Das Bitmuster ersetzt ein ArrayOfBool.
// 3 2 1 0
//10987654321098765432109876543210
//10100000100010100010100010101100
return getBit(0xa08a28ac,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.
};
inline bool isPrime(u32 p)
{
bool isPrimeCheckFactorsAbove5(u32 p);
if(p<32) return isPrimeCheckBelow32(p);
if(!isPrimeCheckFactorsBelow6(p)) return false;
return isPrimeCheckFactorsAbove5(p);
};
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)
{
// 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;
};
namespace
{
u32 primes[]={0,7,7*7,11,11*11,13,13*13,17,17*17,19,19*19,23,23*23,29,29*29,31,-1};
}
bool isPrimeCheckFactorsAbove5(u32 p)
{
{//Zuerst die kleinen Teiler checken
u32 *t=primes;
do
{
if(p%*++t==0) return false;//teilt, also keine Primzahl
}
while(*++t<=p);
if(*t!=-1) return true;
}
return isPrimeCheckFactorsAbove5BySPRPCheck(p);
};
ich vermute, die ist bei vielen zahlen noch ein wenig schneller.
