Bug #89400 for CryptX: Better primality testing in CryptX (libtomcrypt/libtommath)

I've got a bunch of other stuff I need to work on first, but I'll try to make some time for this. Right now I'll add an email with some thoughts. I'll label the steps from your (1): (a) A is a known prime (we know the first N primes) => then PRIME (b) A is divisible by any of the first N primes => then composite (c) A < N-th-prime^2 => then PRIME (here is a bug in code) Yes, step (c) doesn't look right: Given the sizes involved, we should be safe asking if A*A < Pn where Pn is the Nth prime. It should be mixed in with (b). There are lots of ways of doing these steps, each with different performance / readability tradeoffs. MPU::GMP does them in a very simple way, mostly because small values will typically go through the more optimized native-integer methods from MPU. - GCD. With GMP, doing a GCD with a primorial is typically the fastest solution for large inputs. I have no idea for libtommath if this would be true. Thjs is just a speedup over a simple trial division loop. - Steps (b)+(c) with (a) only for tiny values. So something like: if (A < 11) { return (n in (2,3,5,7)) ? 2 : 0 } return 0 if A % 2 == 0 || A % 3 == 0 || A % 5 == 0; for each small prime p starting at 7 { return 1 if p*p > A return 0 if A % p == 0; } return 1 if maxp * maxp < A // note that if maxp goes over 65536 then we need to use isqrt(A) instead. - Use a bit array like MPU's util.c to handle step (a). This stores the first 10,000 primes in 334 bytes. Probably overkill for crypto use as we don't need to shave a couple microseconds off the time for small primes. - Mix (a), (b), (c) together a little. E.g. from MPU's primality.c: if (n < 11) { if (n == 2 || n == 3 || n == 5 || n == 7) return 2; else return 0; } if (!(n%2) || !(n%3) || !(n%5) || !(n%7)) return 0; if (n < 121) /* 11*11 */ return 2; if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || !(n%23) || !(n%29) || !(n%31) || !(n%37) || !(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; if (n < 3481) /* 59*59 */ return 2; This is slightly faster than the simple (b)+(c) but only if we're counting cycles for native integers. I guess we need to know what the goals are: - Fast for small inputs (e.g. under 2^64) - Fast for multi-hundred-digit inputs, especially next_prime - Adequate and simple code Trying to speed everything up adds complication, especially when dealing with multiple size scales. I think just the simple (b)+(c) is best for now. (d) one MR test with base 2 => on failure: composite (e) Lucas test => on failure: composite We have a choice of: - standard Lucas test, as shown in FIPS 186-4 C.3.3. That implementation is not very efficient, by the way. - strong Lucas test. The false positives are a strict subset of the standard test and it runs as fast as the standard test, so honestly there is no reason not to use it. Baillie and Wagstaff's paper recommends this. - extra strong Lucas test or "almost extra strong" Lucas test. See http://www.sti15.com/nt/pseudoprimes.html. Typically faster and fewer pseudoprimes. The weaker version has been used by Pari for years. There are no known pseudoprimes for any of them, and various math packages use different versions. We'd be fine with the any of them, though I don't see why one would use the non-strong test. I chose the extra strong test because it's faster than the standard and strong test, infinitesimally slower than the almost-extra-strong test, and seems to have the strongest result. (f) several MR tests with random base from [2, A-2] => on failure: composite We could put these here or after (d) -- it probably doesn't matter unless the Lucas test is particularly slow relative to the MR test. For the extra tests in MPU's is_prime I chose a number I thought was appropriate based on some probabilities, and chosen not spend too much time. Some people make the argument that we shouldn't bother with any extra tests until we find a BPSW counterexample, but I figured I'd add something. For large inputs (e.g. over 10k digits, so over 33k bits) even a single M-R test takes a noticeable amount of time. For cryptographic purposes I think we shouldn't be quite so dismissive, especially for keys. You could look at what I did in Crypt::DSA::GMP where I'm trying to follow FIPS 186-4 appendix C (for DSA, so table C.1). Their table for RSA isn't nearly as simple. Usually I've used a method like B.3.1.A for random prime generation -- I've never used B.3.1.B, which I believe is trying to make sure p and q are strong primes. Some thoughts: - Why step (d)? Because it means any false positive must be a BPSW counterexample. If we had horrible luck with the random number generator for the random bases, it still must pass base 2. This is, however, my opinion -- I don't think there is consensus on this. - What about duplicates in step (f)? We could store the bases and make sure we choose at least enough independent ones. This is a problem if they ask for 10M bases or something silly. For large sizes it seems overkill anyway, unless our PRNG is hacked. - The number of extra tests is based on the bit size and desired security level. The smaller the size or more security, the more tests. Ideally we'd have a function that takes either A or log2(A) and returns a number of extra tests, then verify that the return values are >= the FIPS values. (g) if all tests pass => then PRIME On Thu, Oct 10, 2013 at 2:26 PM, Karel Miko via RT <bug-CryptX@rt.cpan.org>wrote: Show quoted text