Hi Andrew, thank you for your quick response. > "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. Please don't feel bothered. It is only a technicality with no practical relevance. A couple of years ago I wrote an utility for checksumming a migrated database and I'm just curious if my error estimates hold: they rely on the contract of the prime candidate generator, but if my estimates are off by factor 2 it won't break anything. 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. Oliver
