diff options
| -rw-r--r-- | main.cpp | 27 | ||||
| -rw-r--r-- | primes.cpp | 15 |
2 files changed, 23 insertions, 19 deletions
@@ -144,21 +144,19 @@ void performrsa(){ cout<<"msg = "<<msg2<<endl; } -void fermatpseudo(){ - fillsmallprimes(); - for(int i=2;i<65000;i++){ - if(!strongPseudoPrime2(Bigint(i)))continue; - if(!binary_search(smallprimes.begin(),smallprimes.end(),i))cout<<i<<' '; - } - cout<<endl; -} - -void lucaspseudo(){ +void pseudolist(bool(*func)(const Bigint&)){ fillsmallprimes(); for(int i=2;i<65000;i++){ // cerr<<"TRYING "<<i<<endl; - if(!strongLucasPrime(Bigint(i)))continue; - if(!binary_search(smallprimes.begin(),smallprimes.end(),i))cout<<i<<' '; + bool actualprime=binary_search(smallprimes.begin(),smallprimes.end(),i); + if(!func(Bigint(i))){ + if(actualprime){ + cerr<<"Test misleadingly said that "<<i<<" isn't prime, while it is!"<<endl; + exit(1); + } + continue; + } + if(!actualprime)cout<<i<<' '; } cout<<endl; } @@ -171,7 +169,8 @@ int main(int argc,char **argv){ // performrsa(); // testisqrt(argc,argv); // randprime(Bigint(20),Bigint(42)); - // fermatpseudo(); // strongLucasPrime(Bigint(5)); - lucaspseudo(); + // cout<<strongLucasPrime(Bigint(5777))<<endl; + // pseudolist(strongPseudoPrime2); + pseudolist(strongLucasPrime); } @@ -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; |