3 ms·

From what I've read in the past (and this is borne out by the article you've linked), you wouldn't necessarily use AKS if you need determinism, because there ar

by wging 9y ago

From what I've read in the past (and this is borne out by the article you've linked), you wouldn't necessarily use AKS if you need determinism, because there are other deterministic algorithms with worse asymptotics that perform better on smaller inputs. Has this changed in the last several years? From Wikipedia > While the algorithm is of immense theoretical importance, it is not used in practice. For 64-bit inputs, the Baillie–PSW primality test is deterministic and runs many orders of magnitude faster. For larger inputs, the performance of the (also unconditionally correct) ECPP and APR tests is far superior to AKS. Additionally, ECPP can output a primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm.

YomiK 9y ago
You are correct. AKS (v6, Voloch, or Bernstein) is O(log^6(n)) with large constants. A nice polynomial but both large constants and a larger exponent than we'd like. APR-CL is O(log^K(n)) where K = C*log(log(log(n))), which means for practical purposes it's in the range 3-5, hence has a lower exponent than AKS. As n goes to infinity it does finally exceed AKS, but at that point n is so large as to not be practically computable. ECPP is conjectured O(log^5(n)) or O(log^4(n)) depending on algorithm used. Both Primo and ecpp-dj implementations show O(log^4(n)) growth though the latter doesn't scale well past 1000 digits due to a limited polynomial dictionary. Primo scales very well and has generated results for primes over 30k digits -- much larger than the others. I expect Pari/GP's ECPP implementation to eventually compete nicely when it's ready. Miller-Rabin and BPSW are both O(log^(2+c)(n)), where c is between 0 and 1 depending on the multiplication method, so exponent 2 to 3. But of course these are probabilistic. To my knowledge this has not changed recently. There haven't been substantial improvements to AKS since Bernstein's 2003 paper, which still results in an exponent of 6, though lowers the constant factors by many orders of magnitude. In 2006, Bernstein published a randomized version of AKS which runs in O(log^4(n)). So the same exponent as ECPP but also having the same "downside" of using randomization, and Bernstein notes that it was still slower than ECPP.

by wging 9y ago

YomiK 9y ago

You are correct. AKS (v6, Voloch, or Bernstein) is O(log^6(n)) with large constants. A nice polynomial but both large constants and a larger exponent than we'd like. APR-CL is O(log^K(n)) where K = C*log(log(log(n))), which means for practical purposes it's in the range 3-5, hence has a lower exponent than AKS. As n goes to infinity it does finally exceed AKS, but at that point n is so large as to not be practically computable. ECPP is conjectured O(log^5(n)) or O(log^4(n)) depending on algorithm used. Both Primo and ecpp-dj implementations show O(log^4(n)) growth though the latter doesn't scale well past 1000 digits due to a limited polynomial dictionary. Primo scales very well and has generated results for primes over 30k digits -- much larger than the others. I expect Pari/GP's ECPP implementation to eventually compete nicely when it's ready. Miller-Rabin and BPSW are both O(log^(2+c)(n)), where c is between 0 and 1 depending on the multiplication method, so exponent 2 to 3. But of course these are probabilistic. To my knowledge this has not changed recently. There haven't been substantial improvements to AKS since Bernstein's 2003 paper, which still results in an exponent of 6, though lowers the constant factors by many orders of magnitude. In 2006, Bernstein published a randomized version of AKS which runs in O(log^4(n)). So the same exponent as ECPP but also having the same "downside" of using randomization, and Bernstein notes that it was still slower than ECPP.