Re: BigInteger Prime Generation

Oliver Glier wrote:

>> "On average the probability that a composite number is declared probably prime
>> is significantly smaller than 4 ^ −k. Damgård, Landrock and Pomerance[4]
>> compute some explicit bounds. Such bounds can, for example, be used to
>> generate primes..."
> 
> Does it mean that the prime number generation is correct because the prime tester
> overfullfills its contract (i.e. having failure probability 4^(-k) instead of
> 2^(-k) )? If so, then I think it deserves a comment in the code of the generator.
> Otherwise, I still think the generator needs to increase the certainty (adding
> one is enough) before calling the tester.

No, that's not exactly what I mean, but I'm not expressing myself very well.

It looks like your argument is addressed in Note 4.47 of The Handbook of Applied
Cryptography by Alfred Menezes & al.
http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf

I won't reproduce it all here, but please have a look.

> Please don't feel bothered. It is only a technicality with no practical relevance.

Sure.  It's always worth examining one's assumptions, especially when it comes
to security.

> BTW: I see that BigInteger attributes are non-final. Since the new memory model in
> Java 1.5, making them final would allow to pass instances of BigInteger to other
> threads without synchronization, so making all attributes final might be a good
> idea.

That's an interesting point.  Curiously, they're not final in OpenJDK either.

Andrew.