YomiK · HackerTrans

il y a 8 ansdiscuss

"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

il y a 8 ansdiscuss

"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

il y a 8 ansdiscuss

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

il y a 9 ansdiscuss

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

il y a 9 ansdiscuss

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

il y a 9 ansdiscuss

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

il y a 10 ansdiscuss

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

il y a 10 ansdiscuss

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...

YomiK

il y a 10 ansdiscuss

Not disagreeing, but I think both randomness and primality testing both have the problem that it's so easy to do them poorly. Generating random primes of these sizes isn't all that difficult, and even proofs can be done in reasonable time frames (e.g. under 10 seconds for 1024-bit inputs). There are also a couple random proven prime algorithms which run pretty fast. Getting software to correctly implement everything .... that seems to be hard.

YomiK

il y a 10 ansdiscuss

Could you elaborate on ECPP false negatives? A properly working ECPP should never give false negatives, e.g. return "prime" for a composite. Since ECPP can give a certificate unlike AKS or APR-CL, the caller could do a relatively quick check of the math.

Some proof methods:

- BPSW. Deterministic, completely correct for all 64-bit values. Purely a compositeness test above, though no counterexamples known. This matches the false-positive idea -- above 64-bit it returns one of "definitely composite" or "probably prime."

- BLS 1975 methods. Relies on partial factoring N-1 and/or N+1 so unless the input is a special form, only practical to ~100 digits. No false results if the partial factoring can be done, and even gives a certificate of primality.

- APR-CL. Deterministic. No false results. Fast and practical up to ~5000 digits (one can debate where the impractical size line is). No certificate.

- AKS. Deterministic. No certificate. No false results. Very slow, so not generally used.

- ECPP. Non-deterministic (randomness is used internally), but no false results. Generates a certificate. Primo is practical up to ~30k digits (depends on your hardware and patience, but 10k digits on modern computers is quite practical). Open source implementations aren't as efficient, but still 1k+ digits is very reasonable. It is possible an implementation might be unable to proceed for various reasons and could return "gave up - no primality decision made" in addition to the choices "definitely composite" or "definitely prime (certificate included)". That's really a limitation of the implementation or the caller's patience.

YomiK

il y a 10 ansdiscuss

It is a proven deterministic test of primality. We already had those before AKS, and they are significantly faster than AKS (even the various improvements). But they don't check all the boxes that are useful for stating things in computational complexity proofs without a paragraph of weasel words. So from the theory side of things, it's great since we don't particularly care about the actual execution time, but the asymptotic behavior and whether it is solidly shown to be in P.

Lots of math packages have deterministic primality tests, but none use AKS as a primary method, because AKS offers no benefits over other methods and is many orders of magnitude slower.

For inputs of special form, there are various fast tests. E.g. Mersenne numbers, Proth numbers, etc.

The fastest method depends on the input size and how much work you want to put in. For tiny inputs, say less than 1M, trial division is typically fastest. For 32-bit inputs, a hashed single Miller-Rabin test is fastest. For 64-bit inputs, BPSW is fastest (debatable vs. hashed 2/3 test). The BLS methods from 1975 are significantly faster than AKS up to at least 80 digits, but ECPP and APR-CL easily beat those. ECPP is the method of choice for 10k+ digit numbers, with current records a little larger than 30k digits.

YomiK

il y a 10 ansdiscuss

It's very clever, but obnoxiously slow. It's useful for code golf and as a pretty impressive party trick. But like your banker will not be impressed with your college funding plan of pulling a quarter out of his ear, this is not going to make it in any real use.

Imagine naive absolute-beginner-programmer trial division. This is worse. Now add the overhead of counting via regex backtracking and integer comparison via matching strings. A fair number of regex engines will also start using enormous amounts of memory.

AKS is of theoretical interest, but not really a "normal test." It's very slow in practice, being beat by even decent trial division for 64-bit inputs (it's eventually faster, as expected, but it takes a while). But it is quickly faster than this exponential-time method. The regex is in another universe of time taken when compared to the methods typically used for general form inputs (e.g. pretests + Miller-Rabin or BPSW, with APR-CL or ECPP for proofs).

As others have noted, "has been popularized by Perl" is because it was created by Abigail, who is a well-known Perl programmer (though almost certainly a polyglot). It's also been brought up many times, though it's a nice new blog article. I hope the OP found something better when "researching the most efficient way to check if a number is prime." In general the answer is a hybrid of methods depending on the input size, form, input expectation, and language. The optimal method for a 16-bit input is different than for a 30k-digit input, for example.

comments