aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authortomsmeding <tom.smeding@gmail.com>2016-10-15 09:40:54 +0200
committertomsmeding <tom.smeding@gmail.com>2016-10-15 09:40:54 +0200
commit79ae4ca5d81d7f809cfe282c2b607a27e00f60e5 (patch)
tree142a20bbc688d5fd8f041c52993d55648bb2c1d8
parent519765407150892e2e57929d4c00fc5ea7840529 (diff)
Make strongPseudoPrime2 50% faster
-rw-r--r--primes.cpp23
1 files changed, 19 insertions, 4 deletions
diff --git a/primes.cpp b/primes.cpp
index e0a7e59..73e2b4c 100644
--- a/primes.cpp
+++ b/primes.cpp
@@ -108,11 +108,26 @@ bool strongPseudoPrime2(const Bigint &n){
Bigint nm1(n);
nm1-=1;
Bigint d(nm1);
- while(d.even()){ //TODO: optimise using __builtin_ctz
- d>>=1;
- if(expmod(Bigint::two,d,n)==nm1)return true;
+
+ 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;
+ }
+ Bigint bi(expmod(Bigint::two,d,n));
+ if(bi==1||bi==nm1)return true;
+ for(int i=1;i<zerobits;i++){
+ d<<=1;
+ if(bi==nm1)return true;
}
- if(expmod(Bigint::two,d,n)==1)return true;
+
return false;
}