Document running time of current AKS implementation #7

Open
leto opened this Issue Sep 29, 2012 · 5 comments

Comments

Projects
None yet
3 participants
Owner

leto commented Sep 29, 2012

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 was assigned Sep 29, 2012

Collaborator

bubaflub commented Sep 29, 2012

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).

Owner

leto commented Sep 29, 2012

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.

Owner

leto commented Sep 29, 2012

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

Owner

leto commented Feb 5, 2013

In a nutshell "too freaking slow".

Contributor

danaj commented Feb 5, 2013

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment