[Cryptography] 1023 nails in the coffin of 1024 RSA...

John Denker jsd at av8n.com
Tue Oct 7 15:21:29 EDT 2014


On 10/07/2014 04:14 AM, Jerry Leichter wrote:
>  N/ln N is just an approximation.  For all you know,
> the true number of primes could be only a millionth of that!

I wouldn't have said that.

Actually 
     π(N) > N / (2 + ln N)                        [1]
is a hard lower bound for all N ≥ 2, i.e. for all nontrivial N.

Even tighter bounds exist, but [1] is more than good enough
for present purposes.

Reference:
   http://en.wikipedia.org/wiki/Prime_number_theorem#Bounds_on_the_prime-counting_function


More information about the cryptography mailing list