JDK 8 RFC 7189139 version 2: BigInteger's staticRandom field can be a source of bottlenecks

[Paul Sandoz]

On Oct 4, 2013, at 9:18 AM, Aleksey Shipilev <aleksey.shipilev at oracle.com> wrote:

> On 10/04/2013 03:34 AM, Brian Burkhalter wrote:
>> Here is an alternative solution: http://cr.openjdk.java.net/~bpb/7189139.2/.
> 
> Seems OK with me,

Same here.


> as long as Miller-Rabin test tolerates the
> lower-entropy PRNG.
> 

I think so given recent updates to TLR.


>> If this seems reasonable, does anyone have suggestions as to testing?
> 
> I would like to see the functional tests.
> 
> We can take the list of prime numbers [1] as set P, and then check:
> a) numbers in intersect([2;N), P) return isProbablyPrime=true in more
> than >(1 - 1/2^cert) cases;

Plus the certainty is capped at 100 if the bit length of the big int < 100 (which is the case for the first 50M primes). For large bit lengths it is even less (capped at 4 for > 1024). (IIUC it is (1 - 1/4^N) for N iterations [1], for the impl N = certainty/2.)

Paul.

[1] http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html



> b) all numbers in difference([2;N), P) return isProbablyPrime=false
> 
> N > 50.000.000 would sound convincing.
> 
> -Aleksey.
> 
> [1] http://primes.utm.edu/lists/small/