Thread: faster than LL?
View Single Post
Old 2016-02-06, 13:49   #5
science_man_88's Avatar
"Forget I exist"
Jul 2009

8,369 Posts

Originally Posted by paulunderwood View Post
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.
other than the fact I know x%(2^p-1) = x/(2^p)+x%(2^p) until there's at most p bits I'm not sure how to best do that here. edit: all I can think of is a loop like it's done for the LL code however if N is prime eulerphi(N) =N-1 so the exponent can be reduced to 1 I think as it's usually done mod eulerph if I remember correctly.

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