patternMajor
When is the AKS primality test actually faster than other tests?
Viewed 0 times
theprimalityaksthantestsfastertestactuallywhenother
Problem
I am trying to get an idea of how the AKS primality test should be interpreted as I learn about it, e.g. a corollary for proving that PRIMES ⊆ P, or an actually practical algorithm for primality testing on computers.
The test has polynomial runtime but with high degree and possible high constants. So, in practive, at which $n$ does it surpass other primality tests?
Here, $n$ is the number of digits of the prime, and "surpass" refers to the approximate runtime of the tests on typical computer architectures.
I am interested in functionally comparable algorithms, that is deterministic ones that do not need conjectures for correctness.
Additionally, is using such a test over the others practical given the test's memory requirements?
The test has polynomial runtime but with high degree and possible high constants. So, in practive, at which $n$ does it surpass other primality tests?
Here, $n$ is the number of digits of the prime, and "surpass" refers to the approximate runtime of the tests on typical computer architectures.
I am interested in functionally comparable algorithms, that is deterministic ones that do not need conjectures for correctness.
Additionally, is using such a test over the others practical given the test's memory requirements?
Solution
Quick answer: Never, for practical purposes. It is not currently of any practical use.
First, let's separate out "practical" compositeness testing from primality proofs. The former is good enough for almost all purposes, though there are different levels of testing people feel is adequate. For numbers under 2^64, no more than 7 Miller-Rabin tests, or one BPSW test is required for a deterministic answer. This will be vastly faster than AKS and be just as correct in all cases. For numbers over 2^64, BPSW is a good choice, with some additional random-base Miller-Rabin tests adding some extra confidence for very little cost. Almost all of the proof methods will start out (or they should) with a test like this because it is cheap and means we only do the hard work on numbers which are almost certainly prime.
Moving on to proofs. In each case the resulting proof requires no conjectures, so these may be functionally compared. The "gotcha" of APR-CL is that it isn't quite polynomial, and the "gotcha" of ECPP/fastECPP is that there may exist numbers that take longer than expected.
In the graph, we see two open source AKS implementations -- the first being from the v6 paper, the second including improvements from Bernstein and Voloch and a nice r/s heuristic from Bornemann. These use binary segmentation in GMP for the polynomial multiplies so are pretty efficient, and memory use is a non-issue for the sizes considered here. They produce nice straight lines with a slope of ~6.4 on the log-log graph, which is great. But extrapolating out to 1000 digits arrives at estimated times in the hundreds of thousands to millions of years, vs. a few minutes for APR-CL and ECPP. There are further optimizations which could be done from the 2002 Bernstein paper, but I don't think this will materially change the situation (though until implemented this isn't proven).
Eventually AKS beats trial division. The BLS75 theorem 5 (e.g. n-1 proof) method requires partial factoring of n-1. This works great at small sizes, and also when we're lucky and n-1 is easy to factor, but eventually we'll get stuck having to factor some large semi-prime. There are more efficient implementations, but it really doesn't scale past 100 digits regardless. We can see that AKS will pass this method. So if you asked the question in 1975 (and had the AKS algorithm back then) we could calculate the crossover for where AKS was the most practical algorithm. But by the late 1980s, APR-CL and other cyclotomic methods was the correct comparison, and by the mid 1990s we'd have to include ECPP.
The APR-CL and ECPP methods are both open source implementations. Primo (free but not open source ECPP) will be faster for larger digit sizes and I'm sure has a nicer curve (I haven't done new benchmarking yet). APR-CL is non-polynomial but the exponent has a factor $\log \log \log n$ which as someone quipped "goes to infinity but has never been observed to do so". This leads us to believe that in theory the lines would not cross for any value of n where AKS would finish before our sun burned out. ECPP is a Las Vegas algorithm, in that when we get an answer it is 100% correct, we expect a result in conjectured $O(\log^{5+\epsilon}(n))$ (ECPP) or $O(\log^{4+\epsilon}(n))$ ("fastECPP") time, but there may be numbers that take longer. So our expectation is that standard AKS will always be slower than ECPP for almost all numbers (it certainly has shown itself so for numbers up to 25k digits).
AKS may have more improvements waiting to be discovered that makes it practical. Bernstein's Quartic paper discusses an AKS-based randomized $O(\log^{4+\epsilon}(n))$ algorithm, and Morain's fastECPP paper references other non-deterministic AKS-based methods. This is a fundamental change, but shows how AKS opened up some new research areas. However, almost 10 years later I have not seen anyone use this method (or even any implementations). He writes in the introduction, "Is the $(\lg n)^{4+o(1)}$ time for the new algorithm smaller than the $(\lg n)^{4+o(1)}$ time to find elliptic-curve certificates? My current impression is that the answer is no, but that further results [...] could change the answer."
Some of these algorithms can be easily parallelized or distributed. AKS very easily (each 's' test is independent). ECPP isn't too hard. I'm not sure about APR-CL.
ECPP and the BLS75 methods produce certificates which can be independently and quickly verified. This is a huge advantage over AKS and APR-CL, where we just have to trust the implementation and computer that produced it.
First, let's separate out "practical" compositeness testing from primality proofs. The former is good enough for almost all purposes, though there are different levels of testing people feel is adequate. For numbers under 2^64, no more than 7 Miller-Rabin tests, or one BPSW test is required for a deterministic answer. This will be vastly faster than AKS and be just as correct in all cases. For numbers over 2^64, BPSW is a good choice, with some additional random-base Miller-Rabin tests adding some extra confidence for very little cost. Almost all of the proof methods will start out (or they should) with a test like this because it is cheap and means we only do the hard work on numbers which are almost certainly prime.
Moving on to proofs. In each case the resulting proof requires no conjectures, so these may be functionally compared. The "gotcha" of APR-CL is that it isn't quite polynomial, and the "gotcha" of ECPP/fastECPP is that there may exist numbers that take longer than expected.
In the graph, we see two open source AKS implementations -- the first being from the v6 paper, the second including improvements from Bernstein and Voloch and a nice r/s heuristic from Bornemann. These use binary segmentation in GMP for the polynomial multiplies so are pretty efficient, and memory use is a non-issue for the sizes considered here. They produce nice straight lines with a slope of ~6.4 on the log-log graph, which is great. But extrapolating out to 1000 digits arrives at estimated times in the hundreds of thousands to millions of years, vs. a few minutes for APR-CL and ECPP. There are further optimizations which could be done from the 2002 Bernstein paper, but I don't think this will materially change the situation (though until implemented this isn't proven).
Eventually AKS beats trial division. The BLS75 theorem 5 (e.g. n-1 proof) method requires partial factoring of n-1. This works great at small sizes, and also when we're lucky and n-1 is easy to factor, but eventually we'll get stuck having to factor some large semi-prime. There are more efficient implementations, but it really doesn't scale past 100 digits regardless. We can see that AKS will pass this method. So if you asked the question in 1975 (and had the AKS algorithm back then) we could calculate the crossover for where AKS was the most practical algorithm. But by the late 1980s, APR-CL and other cyclotomic methods was the correct comparison, and by the mid 1990s we'd have to include ECPP.
The APR-CL and ECPP methods are both open source implementations. Primo (free but not open source ECPP) will be faster for larger digit sizes and I'm sure has a nicer curve (I haven't done new benchmarking yet). APR-CL is non-polynomial but the exponent has a factor $\log \log \log n$ which as someone quipped "goes to infinity but has never been observed to do so". This leads us to believe that in theory the lines would not cross for any value of n where AKS would finish before our sun burned out. ECPP is a Las Vegas algorithm, in that when we get an answer it is 100% correct, we expect a result in conjectured $O(\log^{5+\epsilon}(n))$ (ECPP) or $O(\log^{4+\epsilon}(n))$ ("fastECPP") time, but there may be numbers that take longer. So our expectation is that standard AKS will always be slower than ECPP for almost all numbers (it certainly has shown itself so for numbers up to 25k digits).
AKS may have more improvements waiting to be discovered that makes it practical. Bernstein's Quartic paper discusses an AKS-based randomized $O(\log^{4+\epsilon}(n))$ algorithm, and Morain's fastECPP paper references other non-deterministic AKS-based methods. This is a fundamental change, but shows how AKS opened up some new research areas. However, almost 10 years later I have not seen anyone use this method (or even any implementations). He writes in the introduction, "Is the $(\lg n)^{4+o(1)}$ time for the new algorithm smaller than the $(\lg n)^{4+o(1)}$ time to find elliptic-curve certificates? My current impression is that the answer is no, but that further results [...] could change the answer."
Some of these algorithms can be easily parallelized or distributed. AKS very easily (each 's' test is independent). ECPP isn't too hard. I'm not sure about APR-CL.
ECPP and the BLS75 methods produce certificates which can be independently and quickly verified. This is a huge advantage over AKS and APR-CL, where we just have to trust the implementation and computer that produced it.
Context
StackExchange Computer Science Q#23260, answer score: 27
Revisions (0)
No revisions yet.