Quote:
Originally Posted by paulunderwood
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 p2 squarings and subtractions by 2 all mod 2^p1. The test I give requires fewer squarings and some multiplications by 3 all mod 2^p1.

other than the fact I know x%(2^p1) = 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) =N1 so the exponent can be reduced to 1 I think as it's usually done mod eulerph if I remember correctly.