Generate prime of x decimal digits using bit-oriented prime generator

Question

I've got a question on stackoverflow where somebody asks to generate a random 18-digit prime. Unfortunately, the only prime generator is the one from OpenSSL. This prime generator is however geared towards generating primes for RSA and DSA, which means that the only parameter is the size of the prime in bits.

So the question is: how can I generate a prime of x decimal digits using the bit oriented generator? The requirements are that as much as possible of the range is utilized (i.e. the digit at position x being 1..9) and that the chances of a prime is reasonably well distributed over the range (i.e. identical to generating a prime for a generator that would accept x decimal digits as indicator of the range).

It is of course possible to run the prime generator for any of the bit sizes, and it is possible to ask for a re-run as well.

Answer 1

The range of $18$ digit numbers is from $10^{17}$ to $10^{18}-1$. We have $\log_2(10^{17})\approx 56.473, \log_2(10^{18})\approx 59.795$, so the $18$ digit numbers have from $57$ to $60$ bits. First choose the number of bits in your prime. To have an equal chance of choosing any $18$ digit prime, we need to choose the number of bits with a distribution proportional to the number of primes in the range with that many bits. The function PrimePi(n) counts the number of primes below n.

This leads to the following table:

$$\begin {array} {c|c}\text{n}&\text {PrimePi(n)}\\ \hline\\10^{17}&2.55\cdot10^{15}\\2^{57}&3.65\cdot10^{15}\\2^{58}&7.17\cdot10^{15}\\2^{59}&1.410\cdot 10^{16}\\10^{18}&2.413\cdot 10^{16} \end{array}$$

So you want a $57$ bit prime with probability $\frac {3.65-2.55}{24.13-2.55}\approx 0.051$.

Throw a random number to find how many bits you want. If you are not in one of the end brackets, ask for a random prime of that many bits and return the result. If you are in the $57$ bit bracket, keep generating $57$ bit primes until you get one greater than $10^{17}$. If you are in the $60$ bit bracket, generate them until you get one less than $10^{18}$. This should be rather close to equidistribution across the $18$ digit primes.

Answer 2

Are you using Erik Tews' gensafeprime module? If so, there are two issues:

1. All primes generated by this module have the top two bits set. This makes sense in an RSA context, because we need the product of two $n$-bit primes to be $2n$ bits long, not $2n-1$ bits long (there are more sophisticated ways around this problem, but gensafeprime's method is a good practical solution).
2. This module only generates what it calls safe primes, i.e. primes $p$ such that $\frac12(p-1)$ is prime too. This used to be considered a Good Thing (20+ years ago) for arcane number-theoretical reasons, but I think these days the experts regard it as unnecessary.

So you are not getting randomly distributed primes, whatever you do. Therefore it makes no sense to spend too much effort preserving the non-existent randomness of your source primes. In your place, I would use Ross Millikan's method restricted to $56$-, $57$-, and $58$-bit numbers. If you do this, you will never have to discard out-of-range primes, because $1.5 \times 2^{56}$ is an $18$-bit number.

Answer 3

There are $22116397130086627$ primes of $18$ decimal digits. Given a random odd number in the range $[10^{17}, 10^{18}]$, its probability of being prime is about $0.049$. So I wouldn't bother with the OpenSSL prime generator. Just generate pseudo-random integers $x$ with $5\times 10^{16} \le x \le 5 \times 10^{17}-1$ until $2x+1$ is prime: on the average it will take just over 20 tries.