In typical use, primality testing for cryptography is probabilistic. Note that the testing one wants to do in an adversarial condition (where someone else, pos

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.