Thread: faster than LL? View Single Post
2016-02-06, 14:46   #8
paulunderwood

Sep 2002
Database er0rr

24·3·73 Posts

Quote:
 Originally Posted by axn Yes. But even in a properly optimized program (like P95 or PFGW), all squaring will be slightly faster than modular exponentiation with exponents containing lots of 1 bits (I think). Also, all the tests are still probable-primality only (unlike LL test). And the saving of log(p) bits (about 25 bits at current GIMPS LL tests) is just rounding error in the grand scheme of things. One extra OS interrupt, and you won't be able to tell the difference. EDIT:- Not to mention the cost of computing q=(N-1)/p.
I see. Thanks for your analysis.

I coded it up by hacking Robert's script:

Code:
myfermat(p)=mp=2^p-1;q=(mp-1)/p;res=3;len=length(binary(q));forstep(i=len-2,0,-1,res=sqr(res);hi=shift(res,-p);lo=bitand(res,mp);res=lo+hi;if(bittest(q,i),res*=3);while(res>=mp,res-=mp);while(res<0,res+=mp))
Code:
? gettime();myfermat(110503);gettime()
time = 18,232 ms.
18232
? gettime();mylucas(110503);gettime()
time = 18,096 ms.
18096