Thread: faster than LL?
View Single Post
Old 2016-02-06, 14:40   #7
axn's Avatar
Jun 2003

22×5×239 Posts

Originally Posted by paulunderwood View Post
Yes. All squarings. Pari maybe is not the best program to use to see the true differences.
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.

Last fiddled with by axn on 2016-02-06 at 14:42
axn is offline   Reply With Quote