BigInteger Prime Generation

Oliver Glier ogli at ogli.de
Mon Mar 2 22:21:48 UTC 2009


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




More information about the Classpath mailing list