Fix Baillie-PSW!

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;