Various Random things (Was: Java 8 RFC 7189139: BigInteger's staticRandom field can be a source of bottlenecks)

[Alan Eliasen]

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
  eliasen at mindspring.com
  http://futureboy.us/