BigInteger Prime Generation
aph at redhat.com
Tue Mar 3 10:51:43 UTC 2009
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
>> 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.
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
> 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
That's an interesting point. Curiously, they're not final in OpenJDK either.
More information about the Classpath