On Mon, May 26, 2014 at 08:23:07PM +0100, Ben Laurie wrote:
> > Where do you see the bias?
>
> They all work by picking a random number and then stepping upwards
> from that number until a probable prime is found. Clearly, that is
> more likely to find primes with a long run of non-primes before than
> primes with a short run.
I don't think this is an issue. By the prime number theorem for
among $k-bit$ numbers (taking log 2 as a crude approximation of
the natural log) roughly $1/k$ of them are prime. So for 2048 bit
numbers, the gap between primes is about 11 bits.
Consider a 32-bit range in the least significant bits, this contains
~2^21 (~2 million) primes. Our odds of choosing a prime are
proportional to the gap from the previous prime, so the selection
is not uniform leading to less than 21 bits of entropy. Worst case
we deterministically choose a single prime in each such interval,
and lose 20 bits of entropy out of 2048, leaving 2028.
In practice there is a large number of primes with weights near
maximal, and half as many primes with half the weight, ... and the
entropy loss is much smaller.
To choose uniformly, one would have to generate a new random
candidate after each failure, which requires substantially more
random data.
--
Viktor.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majord...@openssl.org
