On Mon, Nov 29, 1999 at 10:10:08AM +0000, Ben Laurie wrote:
>> [...] but OpenSSL only uses 50 rounds of primality testing doesn't
>> it? Which means that only 1 in 2^78 "primes" actually are primes.
> What it means is that there's a 1 in 2^50 chance (or perhaps 1 in 2^100)
> that any particular prime is actually not prime.
Actually not; if you use 50 independent rounds of a test that has a
probability of 50 % per round to detect composite numbers, then
there's a chance of 2^-50 that a given number _which is composite_
will pass all rounds. The proportion of non-prime numbers produced by
a "prime number generator" built on such a test, however, also depends
on the input distribution, i.e. on how many of the candidates are in
prime and how many are composite. Here the prime number theorem
provides an estimate.
But in fact the Rabin-Miller test does much better than the
easily-to-prove 25 % probability (and OpenSSL uses only five rounds of
it after some initial trial divisions). Details on this can be found
in I. Damg�rd, P. Landrock, C. Pomerance: "Average case error
estimates for the strong probable prime test" [Math. Comp. 61 (1993)
177-194].
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
