aboutsummaryrefslogtreecommitdiff
path: root/primes.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'primes.cpp')
-rw-r--r--primes.cpp15
1 files changed, 10 insertions, 5 deletions
diff --git a/primes.cpp b/primes.cpp
index c9d25c0..d259939 100644
--- a/primes.cpp
+++ b/primes.cpp
@@ -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;