Re:A prime number whose binary representation looks like a g...
by SAI_Peregrinus on Saturday January 20, 2018 @10:16AM
(#16193604)
Lenstra 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.
[ Parent
| on HN ]
Re:A prime number whose binary representation looks like a g...
by YomiK on Monday January 22, 2018 @02:20PM
(#16207077)
"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.