ACTUALLY fix strongPseudoPrime2

1 files changed, 6 insertions, 13 deletions

diff --git a/primes.cpp b/primes.cpp
index 73e2b4c..77d547f 100644
--- a/primes.cpp
+++ b/primes.cpp
@@ -109,22 +109,15 @@ bool strongPseudoPrime2(const Bigint &n){
 	nm1-=1;
 	Bigint d(nm1);
 
-	int zerobits=0;
-	while(d.even()){
-		Bigint::slongdigit_t lowdig=d.lowdigits();
-		int trzeros;
-		if(lowdig==0){
-			trzeros=8*sizeof(Bigint::slongdigit_t)-1;
-		} else {
-			trzeros=__builtin_ctz(d.lowdigits());
-		}
-		zerobits+=trzeros;
-		d>>=trzeros;
-	}
+	int zerobits=d.trailingZeros();
+	d>>=zerobits-1;
+	assert(d.even());
+	d>>=1;
+	assert(d.odd());
 	Bigint bi(expmod(Bigint::two,d,n));
 	if(bi==1||bi==nm1)return true;
 	for(int i=1;i<zerobits;i++){
-		d<<=1;
+		bi=(bi*bi).divmod(n).second;
 		if(bi==nm1)return true;
 	}