This question already has an answer here:

kinda new here, I had a question pertaining to someone being able to factor one's RSA keys through the GCD. Anyways the question goes that there are two people: A and B. A makes his/her private key as $N_a = p_a\cdot q_a$ and B does the same with $N_b = p_b \cdot q_b$. I'm assuming here that both random primes are of length n bits and so I'm wondering whats the probability of the two keys sharing a common prime. I was considering that it may have something to do with the Prime number theorem but not entirely sure.


marked as duplicate by SEJPM, otus, Gilles, e-sushi Mar 27 '16 at 2:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ remember that PNT is an asymptotic distribution, so your probability will be approximate. That said, sounds like you are on the right track. What is the probability that one of the probability that the intersection of $\{p_a,q_a\}$ and $\{p_b,q_b\}$ is non-empty? $\endgroup$ – mikeazo Dec 10 '14 at 16:14
  • $\begingroup$ I understood that but I'm just having a problem connecting it to the n bit length. $\endgroup$ – Marorin Dec 10 '14 at 16:32
  • $\begingroup$ Well, a $n$-bit number lies between $2^{n-1}$ and $2^n-1$ (inclusive). $\endgroup$ – fkraiem Dec 10 '14 at 16:49
  • 1
    $\begingroup$ If $\pi(x)$ is the number of primes less than $x$ (which $x/\ln(x)$ approximates), then it would be $\pi(2^n-1)-\pi(2^{n-1})$. So you can approximate it using the formula. $\endgroup$ – mikeazo Dec 10 '14 at 18:00
  • 3
    $\begingroup$ Similar question: How many RSA keys before a collision? $\endgroup$ – CodesInChaos Dec 11 '14 at 9:12

Browse other questions tagged or ask your own question.