diff options
Diffstat (limited to 'primes.cpp')
-rw-r--r-- | primes.cpp | 19 |
1 files changed, 6 insertions, 13 deletions
@@ -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; } |