# Generating Random Primes

Although this has been extensively discussed around here, I'm curious whether my approach makes sense, or I should just stick to "the standard version".

I'm implementing some homomorphic encryption primitives (Paillier, Okamoto–Uchiyama etc) and, at the moment, I'm using GMP as the big number library (this may change in the future). GMP has a function called mpz_nextprime and I generate random numbers, after which I call this function on them, to get prime numbers. Is this a good approach? The other alternative would be to just generate random numbers in a loop, until mpz_probab_prime_p(number, 10) says that they are prime. This latter approach seems rather wasteful though, from a programmer's point of view.

How do you generate prime numbers with GMP or OpenSSL (or other crypto libraries like cryptlib, crypto++, etc)? I am unsure how the mpz_nextprime function works or if other libraries provide such functionality... Ideally, I should be able to just swap various big number libraries in my implementation, without changing the prime generator wrapper.

-
crypto.stackexchange.com/a/1971/706, I'm betting that this is what mpz_nextprime does. It is what OpenSSL does. –  mikeazo May 3 '12 at 19:22
This question appears to be off-topic because it is about using cryptographic libraries (Crypto++, OpenSSL etc.) and using them in an application. According to our help center, this fits better at Stack Overflow. –  e-sushi Mar 23 at 3:00
Well, I did get a really good answer here, so I can't complain. Also, my question was more about the general algorithmic approach of generating prime numbers. I used the libraries as mere examples. –  Mihai Todor Mar 23 at 3:14

Now, regarding the method: A potential problem with generating a random number and then "walking" to the next largest prime is that primes are not evenly distributed, so neither are the gaps between them. If you have consecutive primes $p_i$ and $p_{i+1}$, any randomly generated number between $p_i$ and $p_{i+1}$ would get mapped to $p_{i+1}$. Primes that follow large gaps are more likely to be chosen, and primes that follow smaller gaps would be less likely to be chosen. You would be imposing a non-uniform distribution on your choice of primes. (Read a little more here.)
That isn't necessarily a problem, though, and I can't say I've ever seen serious concern raised over it. OpenSSL probably has sufficient confidence in their method. Although, of course, the "perfect" way to ensure your have a prime number distribution that is even is to just generate random numbers until one of them is prime. Although it is probably a little slower than "increment-and-test" on average, it can't be much slower. One advantage of the increment-and-test method that it is deterministic, since there is guaranteed to be a prime between $p$ and (approximatively) $p + \sqrt(p)$, but given the frequency of primes ($log(p)$), I would think that such weak work limit wouldn't be a concern.
Here is an approach to select a random prime nearly free of bias. Say that for some $a,b$ with $2≤a≪b$ we want a random prime $p$ with $a≤p<b$. Pick a random $s$ with $0<s<b-a$ until $\gcd(s,b-a)=1$. Pick a random $t$ with $0≤t<b-a$. Use for $p$ the first prime among the $p_i=(i⋅s+t)\bmod(b-a)+a$. Simple variants can be made to select prime $p$ such that $p-1$ has a big known prime factor $s$, or/and such that $p+1$ has another big known prime factor, see e.g. FIPS 186-4 section B.3.6. –  fgrieu Mar 24 at 12:02