search

leto / math--primality

Advanced primality-checking algorithms
http://duke.leto.net
8 stars 13 forks source link

Document running time of current AKS implementation #7

Open leto opened 12 years ago

leto commented 12 years ago

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 commented 12 years ago

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 commented 12 years ago

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 commented 12 years ago

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

leto commented 11 years ago

In a nutshell "too freaking slow".

danaj commented 11 years ago

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.