2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – fgrieu ♦
    Oct 17, 2013 at 11:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – tylo
    Oct 17, 2013 at 11:30

1 Answer 1

Reset to default
2
$\begingroup$

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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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