Thread: faster than LL?
View Single Post
Old 2016-02-06, 13:43   #4
paulunderwood's Avatar
Sep 2002
Database er0rr

25·109 Posts

Originally Posted by science_man_88 View Post
it will depend on which version or coding of the LL test you use to test it against on my system for exponent 110503 your code runs for 1min, 29,975 ms. the lucas example takes about 2min, 17,097 ms. and the code from runs in under 29 seconds.
29 seconds is because of the special mod 2^p==1 has been used. Try applying that to my fractional power Fermat PRP test!

The LL tests uses p-2 squarings and subtractions by 2 all mod 2^p-1. The test I give requires fewer squarings and some multiplications by 3 all mod 2^p-1.

Last fiddled with by paulunderwood on 2016-02-06 at 13:51
paulunderwood is offline   Reply With Quote