YomiK · HackerTrans

8 yıl öncediscuss

"Perhaps this work will finally prompt widespread change."

I sure hope so. I've argued this to various languages and libraries for a few years, and mostly they don't really care, other than they've heard of M-R and not of anything else.

One bottleneck I ran into are the "Prove that the probability is smaller" argument. The probability bound for BPSW is actually not very good, but empirically we see that bound is grotesquely conservative. One can always add more random-base M-R tests if desired.

There is also the problem that statistical thinking is hard for people. This comes up with using fixed bases and not grasping that this ruins the "2^-80 probability!" (for example) claim. That only applies to a random input.

YomiK

8 yıl öncediscuss

"not as slow as pre-AKS methods." only in terms of provable asymptotic bounds. It's much slower than APR-CL and ECPP, both of which existed before AKS, and are the methods used daily.

YomiK

8 yıl öncediscuss

Pari/GP's APR-CL took 4 seconds to prove it. Perl's ntheory module took 2.6 seconds to prove with ECPP (including generating and verifying a certificate). That's over 1000x slower than BPSW but still not bad.

YomiK

9 yıl öncediscuss

You are correct.

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.

YomiK

9 yıl öncediscuss

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.

YomiK

9 yıl öncediscuss

This is incorrect.

"prime numbers would be too easy to find" -- they're already really easy to find. Factoring large semiprimes is currently hard. Primality testing and finding primes for RSA keys is very easy. If the RH was proven true, it wouldn't speed that up in any practical way either.

As an experiment, assume the Riemann Hypothesis. Does that make factoring easier? No. Do we have any currently known methods of weakening RSA if the RH was true? No.

For some actual consequences of the RH: https://mathoverflow.net/questions/17209/consequences-of-the...

YomiK

10 yıl öncediscuss

Hart's OLF:

http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S144678871200014...

is an interesting variant. Like Caroline mentioned, you won't have any success with this on properly formed RSA keys, but Hart's OLF will very quickly factor some poorly made ones, and works quite a bit better in that respect than standard Fermat. It not only quickly finds N=PQ where P=Q+x for a small x, but also where P=kQ+x for some integer k and small x. Again not something any proper RSA key generation method will produce, but the ways people can screw things up is pretty high, and it might be worth giving it a few seconds just in case.

For small values, unlike Hart I find SQUFOF to be faster, but this is implementation specific. HOLF is also, like Fermat's method, extremely simple to implement.

YomiK

10 yıl öncediscuss

There are many such formulas, such as Willan's 1964 simple formula for the nth prime. But they are basically all hiding a sieve, Wilson's theorem, the prime count function, or some other calculation. That is, none of them are at all practical, and most offer no insight.

I'd recommend perusing "Formulas for Primes" by Underwood Dudley, 1983. Free online link: http://www.maa.org/programs/faculty-and-departments/classroo...

comments