3 ms·
Sometimes its a good idea to use a faster probable prime test when searching, and then use a slower test to verify the result. As has been done here.
by phkahler 9y ago
Sometimes its a good idea to use a faster probable prime test when searching, and then use a slower test to verify the result. As has been done here.
- SAI_Peregrinus 9y agoLenstra and Pomerace's variant of the AKS test is O(log(n)^6), and deterministic. So polynomial, and not a huge exponent. Still not as fast as the probabilistic algorithms, but not as slow as pre-AKS methods.
- YomiK 9y ago"not as slow as pre-AKS methods." only in terms of provable asymptotic bounds. It's much slower than APR-CL and ECPP, both of which existed before AKS, and are the methods used daily.