# Prime number theorem - RSA

I am having trouble understanding the prime number theorem.

As part of some revision for an exam, I am trying to answer the following questions (but seeing as I don't understand the concept of the prime number theorem, I'm not doing too well):

Question 1:

What is the proportion of numbers that are prime up to 1,000,000?

Question 2:

If we use prime numbers of size 1536 bits to generate an RSA modulus of 3072 bits, what is the proportion of numbers of size 1536 bits that are prime numbers?

I understand that using 1536 bits means that is it pretty much computationally infeasible to stage a brute force attack on an RSA key, but I don't understand why. In our lectures, we are given an example of $ln (2^{512}) = 355$ which means that 1 in every 355 numbers of size 512 bits is a prime. But I'm not really sure how to translate that to help with the two aforementioned questions.

Can anyone please shed some light and explain the answers to those questions?

• The answer to q1 as worded is: $\Pi(10^6)/10^6=39249/500000$, $\Pi(10^6)/(10^6+1)=78498/1000001$, or $0$, depending on how number is read. But the actual question you are asked is: Using the Prime Number Theorem, estimate the proportion of positive integers up to 1,000,000 that are prime. That's a straight application of the Prime Number Theorem. Hint for q2: what's the difference between the number of primes of size at most $n$ bits, and the number of primes of size exactly $n$ bits? – fgrieu Oct 17 '13 at 11:12
• Concerning your lecture example, there is a small mistake: $\ln(2^{512})\approx 355$ means, that there are (estimated) around $2^{512} / 355$ prime numbers up to $2^{512}$ . As fgrieu pointed out, the number of 512 bit primes is a little lower, since you have to get rid of the numbers which are smaller. Additionally, there are only $2^{512}-2^{511}=2^{511}$ numbers in total with 512 bit. Concering your 2nd question: You can safely ignore the first part (about RSA modulus) of the question, it is completely irrelevant for the proportion of primes with exactly 1536 bit. – tylo Oct 17 '13 at 11:30

Apply your formula, perhaps simplified as $\ln(2^x)={x} \ln(2)$, so for 1536-bit numbers about one in $1536 \ln(2)$ are prime. In the case of $1{,}000{,}000=2^{20}$ (approx.) the number of primes is about one in $20 \ln(2)$.