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.

  • $\begingroup$ Seems obvious now. I knew this was a silly question. Thanks! $\endgroup$
    – forest
    Jun 18 '19 at 2:35
  • $\begingroup$ 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. $\endgroup$ Jun 18 '19 at 12:38
  • 2
    $\begingroup$ @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. $\endgroup$ Jun 18 '19 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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