We can make primality machines that do not know anything about the factors of n

https://mathlesstraveled.com/2018/01/03/a-tale-of-three-machines/

by ColinWright • 9 years ago

19 5 9 years ago

l0b0• 9 years ago

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?

[1] Citation needed. This was years ago :/

johncolanduoni• 9 years ago

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.

[1] https://en.m.wikipedia.org/wiki/AKS_primality_test

wging• 9 years ago

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.

YomiK2• 9 years ago

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.

We can make primality machines that do not know anything about the factors of n

Related Stories