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.