Document running time of current AKS implementation

[leto]

There are various optimizations for the AKS algorithm but if I recall correctly, the "naive" AKS algorihm is O(n^12). @bubaflub, can you add some info to the Math::Primality::AKS pod about the approximate running time of the current implementation?

[bubaflub]

Correct, the heaviest part of the algorithm is where we do the polynomial modular reduction for a range of values of r. The initial paper was O(n^12). Daniel Bernstein has a paper where he tightens the bounds on r resulting in a running time of O(n^6).

[leto]

Awesome. Just for reference, benchmarks on my machine tell me that is_aks_prime is about 3 times faster than is_prime for "smallish" numbers (~10^10). I haven't been able to get good results for large-ish numbers (~10^50), but I assume is_aks_prime will shine even more. It would be very exciting to have the O(n^6) algorithm implemented. That might make us the fastest primality algorithm on CPAN.

[leto]

DJB paper mentioning AKS optimizations: http://cr.yp.to/papers/aks.pdf

[leto]

In a nutshell "too freaking slow".

[danaj]

Page 8 of the DJB paper referenced: "Of course, 'two million times faster' does not mean 'fast'". For improvements, 1) reduce the r value as much as possible, 2) implement fast polynomial modular exponentiation. I suspect even with all that all you get is "not completely intolerable". His 2006 paper is the one with the competitively fast algorithm though I haven't seen any more about practical AKS implementations since then. I think most people went to work on ECPP.