View Single Post
Old 2019-08-13, 20:11   #4
kriesel's Avatar
Mar 2017
US midwest

5,119 Posts

Originally Posted by ixfd64 View Post
It is my understanding that double an exponent results in an LL test taking approximately four times longer.
So does the time complexity for LL tests stop exhibiting quadratic growth after a certain point? Or is there an error in the calculator?
The number theory folks tell us it's O(p2 log p log log p) per primality test using the best available technology for this size multiplication or squarings mod Mp, the irrational base discrete weighted transform. Over the range, that works out to around p2.117. Double the exponent, about 4.34 times the effort.
Empirical run time scaling for LL, PRP, or P-1 are around p2.1. Any fixed overhead appears to lower the power on the scaling and have greater effect in lowering the scaling power at small p.
prime95 PRP
prime95 P-1

Last fiddled with by kriesel on 2019-08-13 at 20:12
kriesel is online now   Reply With Quote