I'm pretty sure I've read[1] that primality machines in normal computers rely on a heuristic to determine whether the factors produced are very, very likely to be prime, and that security focussed organisations subsequently use large amounts of computation (on the order of several days on a supercomputer) to verify that the factors are, in fact, prime. Or is there a class of super fast algorithms which guarantee primality as the author implies?
There is AKS[1], which is deterministic and polynomial time. The most common need for a primality test is the generation of RSA keys, where a mistake will result in a key that almost certainly doesn’t work (I.e. you can’t decrypt encrypted data even if you have the correct half of the key). For these cases a faster probabilistic test is still the most popular.
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.
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.
In typical use, primality testing for cryptography is probabilistic. Note that the testing one wants to do in an adversarial condition (where someone else, possibly nefarious, is giving you input) would be far more stringent than typical crypto prime generation where you supply the inputs. The chance of randomly chosen composite of the size we use for crypto passing even a single Miller-Rabin test is extraordinarily low. Use multiple random bases and ideally add a strong Lucas test, and one can be reasonably certain the result is prime. Not certain enough for mathematicians, but enough that you've exceeded the security of other areas in your method.
There are reasonably primality proving methods, such as ECPP and APR-CL, that can give results in quite reasonable times. As in under 30 seconds using a single core of a home computer for a 2048-bit prime. There's no need to invoke supercomputers and days of time. BPSW (a good probable prime test) takes under 10 milliseconds for this size input.
Related to the original article, all these times are ridiculously fast compared to the time it would typically take to factor 600 digit composites using current state of the art methods.
AKS is often mentioned on internet forums. It's not actually used -- it's horribly slow. Estimated time of about 17 years for those inputs that take less than 30 seconds with the other exactly as good methods. Unless you're writing a paper that needs a theoretical asymptotic complexity result for primality, or doing number theory research and reading the actual paper for the math, there is almost no reason to invoke AKS.
So ... why don't people use the proofs?
(1) in a practical sense there is basically no value. BPSW is extremely fast (M-R base 2 plus strong Lucas) and there are no known counterexamples after 38 years of use. It's what is used by Pari/GP, Mathematica, etc. You can add a few more M-R tests to reduce the chance even further (as FIPS 186-4 recommends for crypto use).
(2) crypto *programs* are almost all written by programmers, not mathematicians. Most of them have never heard of anything beyond Miller-Rabin.
(3) Coding Miller-Rabin is quite simple. It's 10-25 lines of code, and written in hundreds of books. It's fairly easy to write correctly, and easy for others to double check. Coding APR-CL or ECPP is quite difficult. Open source implementations for both are over 1000 lines, and verifying that they actually work is difficult. ECPP can give a primality certificate that can be verified so that is helpful, but there are still many more areas to screw something up. A working and solid probable primality test is *more* certain than a badly coded primality proof implementation.
6 comments
[ 4.4 ms ] story [ 21.0 ms ] thread[1] Citation needed. This was years ago :/
[1]: https://en.m.wikipedia.org/wiki/AKS_primality_test
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.
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.
There are reasonably primality proving methods, such as ECPP and APR-CL, that can give results in quite reasonable times. As in under 30 seconds using a single core of a home computer for a 2048-bit prime. There's no need to invoke supercomputers and days of time. BPSW (a good probable prime test) takes under 10 milliseconds for this size input.
Related to the original article, all these times are ridiculously fast compared to the time it would typically take to factor 600 digit composites using current state of the art methods.
AKS is often mentioned on internet forums. It's not actually used -- it's horribly slow. Estimated time of about 17 years for those inputs that take less than 30 seconds with the other exactly as good methods. Unless you're writing a paper that needs a theoretical asymptotic complexity result for primality, or doing number theory research and reading the actual paper for the math, there is almost no reason to invoke AKS.
So ... why don't people use the proofs?