On 09/04/2013 05:26 PM, Brian Burkhalter wrote: > I have updated the webrev > > http://cr.openjdk.java.net/~bpb/7189139/ > > to add the two-parameter version of isProbablePrime() which was > discussed. Naturally a CCC request would be needed in the event this > were to go forward.
The change to pass in the random number generator appears fine. There's probably no need for a strong random number generator in this case, though. Rabin-Miller is a robust algorithm and the probability of its failure can be easily made so that it's far more probable that the computer's hardware fails while running the test. (I wrote an article about this if you're interested.) The particular random numbers that it chooses are not terribly crucial as long as there's enough margin, and as long as random numbers aren't repeated pathologically. However, the primality tests could be made more efficient and more certain. For smallish numbers, the Rabin-Miller test performs a large number of random tests, with some low probability of failure. It's known, however, for numbers less than 341,550,071,728,321, (or larger, see references below,) that there are minimal sets of bases we need to test with a Rabin-Miller test to *prove* primality. (This would also allow us to eliminate generating random numbers entirely, in these cases, to perform a much smaller number of Rabin-Miller rounds, and let us skip the Lucas test entirely as well, and enable a *proof* of primality for numbers smaller than this.) For example, if the number n is less than 4,759,123,141 (this encompasses all ints) then you only need to test that n is a strong probable prime to bases 2,7, and 61 to *prove* primality. This would be much faster than the code now (which may do 50 rounds, and won't do *more* than 50 rounds, no matter what certainty you request, which is almost certainly a bug in the current code.) It would also be more correct than the current code, which admits a low probability of failure. There are references which show the exact bases to test for smaller numbers in a Rabin-Miller test to *prove* primality here: http://primes.utm.edu/prove/prove2_3.html#quick http://priv.ckp.pl/wizykowski/sprp.pdf http://math.crg4.com/primes.html http://www.gpgpgpu.com/gecco2009/6.pdf Further, to *prove* primality of everything that will fit into an unsigned long (2^64), you only need to test all prime bases <= 37. See: http://oeis.org/A014233 There could be a fast path to do the tests for smallish numbers in a long or an int. You'll want a modPow function. Here's one for ints: /** Compute x^y mod m. Assumes m >= 2. */ public static int modPow(int x, int y, int m) { long acc = 1; long z = x % m; while (y != 0) { if ((y & 1) != 0) acc = (acc * z) % m; z = (z * z) % m; y >>= 1; } return (int) acc; } -- Alan Eliasen elia...@mindspring.com http://futureboy.us/
