On Sep 5, 2013, at 7:02 AM, Alan Eliasen <elia...@mindspring.com> wrote:
> 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. > If that is the case why not just leave the method as is and replace SecureRandom with ThreadLocalRandom? > 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.) Right, but IIUC 50 rounds will result in a probability of 1 - 1 / 4^50 that the number under test is a prime. If so is there any point in more rounds? we could just clarify the docs. Paul. > 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/
