Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Say I want a random 1024-bit prime $p$. The obviously-correct way to do this is select a random 1024-bit number and test its primality with the usual well-known tests.

But suppose instead that I do this:

  1. select random odd 1024-bit number $n$
  2. if $n$ is prime, return $n$
  3. $n \leftarrow n+2$
  4. goto 2

(This approach allows faster selection of primes via sieving.)

Since primes are not uniformly distributed on the number line, it would seem that this algorithm prefers primes that lie after long runs of composites. Take a piece of the number line around $2^{1024}$ with x denoting a prime:

---x-x----------------------------x------------------------x---x

Clearly our algorithm above is much more likely to find the 3rd prime above than to find the 2nd one.

Question: Is this a problem?

share|improve this question
1  
The question is that a problem can be sidestepped by replacing n<-n+2 by n<-n+m for some even m, drawn at random at the beginning of the procedure. This still allows fast selection of primes via sieving. It is sometime done with m=2*p for some random prime p, and allows to enumerate only those n such that p divides n-1. –  fgrieu Sep 16 '11 at 1:48
add comment

2 Answers

up vote 10 down vote accepted

This procedure is known as incremental search and his described in the Handbook of Applied Cryptography (note 4.51, page 148). Although some primes are being selected with higher probability than others, this allows no known attacks on RSA; roughly speaking, incremental search selects primes which could have been selected anyway and there are still gazillions of them. OpenSSL uses this prime generation technique.

share|improve this answer
add comment

No, it is not believed to be a problem, probably because:

  • No known factoring method can take advantage of the bias

  • The bias really isn't that large, at least, when you compare it to the number of primes. Given the density of primes around 2^1024, there are likely primes that come immediately after 2000 consecutive odd composites; such a prime would have a probability of about 2000/2^1022 ~ 2^-1011 of being chosen. On the other extreme, a prime that comes immediately after another prime (a twin prime) would have a probability of 2^-1022 of being chosen. There wouldn't appear to be that much difference between 2^-1011 and 2^-1022.

In addition, the existing standards for finding primes (X9.31, X9.80) endorse the above type of linear search (even if they differ in some of the details, such as having the increment not being two, but some other even number).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.