News for hackers. Stuff that matters.

A comment on A prime number whose binary representation looks like a giraffe. Parent comment

Re:A prime number whose binary representation looks like a g... by phkahler on Saturday January 20, 2018 @07:38AM (#16193140)
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.
[ Parent | on HN ]
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.
[ Parent | on HN ]