# Distribution of safe primes generated using different techniques

Is there any difference in the distribution of safe primes generated by creating prime $$q$$ and testing $$2q+1$$ for primality, compared to generating a larger prime $$p$$ and testing $$(p-1)/2$$ instead? The former is what is used in practice for efficiency. For the purposes of this question, I am assuming primality is determined by creating an odd integer, subjecting it to a sufficient number of Miller-Rabin tests, and incrementing it by two if it is composite before testing it again.

$$\{p \in \mathbb Z \mid \text{p is prime and (p - 1)/2 is prime}\} = \{2q + 1 \in \mathbb Z \mid \text{q is prime and 2q + 1 is prime}\}$$

With your intervals suitably adjusted, the algorithm considers the same candidates with the same probability whether you check $$p$$ or $$q$$ for primality first.

• Seems obvious now. I knew this was a silly question. Thanks! – forest Jun 18 at 2:35
• While this is mathematically true (+1), there is still a minor issue hidden in "intervals suitably adjusted". It is at least conceivable that a given algorithm using a pseudorandom number generator might behave sufficiently different on different intervals so that the generated primes follow a slightly different distribution. Whether or not that would be exploitable (which I highly doubt) is a different question. – John Coleman Jun 18 at 12:38
• @JohnColeman If there were a way to distinguish that from uniform random, then the mere act of searching for RSA moduli with it would break the pseudorandom generator, so it wouldn't be a very good pseudorandom generator. – Squeamish Ossifrage Jun 18 at 13:30