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

[Paul Sandoz]

On Sep 5, 2013, at 7:02 AM, Alan Eliasen <eliasen at 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
>  eliasen at mindspring.com
>  http://futureboy.us/