diff options
Diffstat (limited to 'primes.cpp')
| -rw-r--r-- | primes.cpp | 15 |
1 files changed, 10 insertions, 5 deletions
@@ -113,7 +113,9 @@ Bigint randprime(const Bigint &biglow,const Bigint &bighigh){ bool strongPseudoPrime2(const Bigint &n){ //https://en.wikipedia.org/wiki/Strong_pseudoprime#Formal_definition - if(n<2||n.even())return false; + if(n<2)return false; + if(n==2)return true; + if(n.even())return false; Bigint nm1(n); nm1-=1; Bigint d(nm1); @@ -128,6 +130,8 @@ bool strongPseudoPrime2(const Bigint &n){ bool strongLucasPrime(const Bigint &n){ //https://en.wikipedia.org/wiki/Lucas_pseudoprime#Implementing_a_Lucas_probable_prime_test //TODO: use d and s already calculated in strongPseudoPrime2 + if(n<2)return false; + if(n==2)return true; if(n.even())return false; int D; if ((D= 5),jacobiSymbol(Bigint(D),n)==-1); @@ -146,13 +150,14 @@ bool strongLucasPrime(const Bigint &n){ //now we have a D // cerr<<"D="<<D<<endl; int P=1,iQ=(1-D)/4; - if(gcd(n,Bigint(P))!=1||gcd(n,Bigint(iQ))!=1)return false; //would be too easy to ignore + if(gcd(n,Bigint(P)).compareAbs(1)!=0||gcd(n,Bigint(iQ)).compareAbs(1)!=0)return false; //would be too easy to ignore + // cerr<<"ok"<<endl; //now begin the actual sequence algorithm -#if 1 +#if 0 int s=0; Bigint d(n); - d-=1; + d+=1; while(d.even()){ d>>=1; s++; @@ -193,8 +198,8 @@ bool strongLucasPrime(const Bigint &n){ } } if(U==0)return true; +#if 0 if(V==0)return true; //r=0 check -#if 1 for(int r=1;r<s;r++){ V*=V; V-=Qk<<1; |