When calculating prime numbers $p$ and $q$ for an RSA private key, one of the requirements is that $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, where $e$ is the RSA exponent (typically 65537).

I'm curious how often it happens in practice that a randomly generated prime number happens to not satisfy $\gcd(p-1,65537)=1$. Are the chances of this happening related to the size of the prime number?


If you generate a prime randomly, and then check, it happens with probability $1/65536$.

On the other hand, it is common practice to include the criteria $p \not\equiv 1 \pmod {65537}$ as part of the prime search; if you do that, the probability is 0.

| improve this answer | |
  • $\begingroup$ To whoever 'corrected' this, the probability really is 1/65536, not 1/65537 $\endgroup$ – poncho Sep 7 '17 at 21:40
  • $\begingroup$ @yyyyyyy: that's because if $p$ is a prime other than $65537$, then $65537$ does not divide $p$, hence $p-1\bmod65537\ne65536$. Rather, for random $p$, the integer $p-1\bmod65537$ is equidistributed on $[0,1,\dots,65534,65535]$ (under some hypothesis cousin to Riemann's, generally believed to hold at least for cryptographic purposes). Primes used in RSA are often with $p\bmod4=3$ because that simplifies the primality test, but everything still applies if we restrict to these primes. $\endgroup$ – fgrieu Sep 8 '17 at 9:48
  • 1
    $\begingroup$ @fgrieu: actually, that it's equidistributed has been proven by de la Vallée-Poussin; no unproven hypothesis needed... $\endgroup$ – poncho Sep 8 '17 at 9:59
  • $\begingroup$ Often I wish I had really studied math, rather than math-for-the-electronics-and-computer-science-engineer; and had more than a skin-deep understanding of number theory. $\endgroup$ – fgrieu Sep 8 '17 at 10:12
  • 1
    $\begingroup$ @poncho Sorry, my bad. I seem to have forgotten for a moment that primes are almost never divisible by 65537... $\endgroup$ – yyyyyyy Sep 9 '17 at 14:52

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.