Prime distribution

[Robert J. Hansen]

A couple of days ago dkg posted a back of the envelope calculation about
the number of 2048-bit primes out there.  (Anybody who thinks that's
perjorative is crazy.  His answer was both quick and pretty accurate.  I
think he'd agree it was a good BOTEC.)

Anyway.  The use of pure integer arithmetic gave my inner mathematician
the heebie-jeebies, and I had some time while waiting on the car repair
shop to give me some news about my rear differential, so... I figured to
do it the right way, with logarithms.  :)  I used the same prime
distribution formula dkg did (Euler's n/ln n estimate).

Note: due to vagaries of floating-point behavior, this table is not
perfectly accurate.  And Euler's estimate is just an estimate, anyway.

              +-------+------------------+------------------+
              | Bits  |    In base-10    |    # of primes   |
              +-------+------------------+------------------+
              | 512   | 1.341 * 10**154  | 3.778 * 10**151  |
              | 768   | 1.553 * 10**231  | 2.916 * 10**228  |
              | 1024  | 1.798 * 10**308  | 2.533 * 10**305  |
              | 1280  | 2.082 * 10**385  | 2.346 * 10**382  |
              | 1536  | 2.41  * 10**462  | 2.264 * 10**459  |
              | 1792  | 2.791 * 10**539  | 2.247 * 10**536  |
              | 2048  | 3.232 * 10**616  | 2.277 * 10**613  |
              | 2304  | 3.742 * 10**693  | 2.343 * 10**690  |
              | 2560  | 4.333 * 10**770  | 2.442 * 10**767  |
              | 2816  | 5.017 * 10**847  | 2.57  * 10**844  |
              | 3072  | 5.81  * 10**924  | 2.728 * 10**921  |
              | 3328  | 6.727 * 10**1001 | 2.916 * 10**998  |
              | 3584  | 7.789 * 10**1078 | 3.136 * 10**1075 |
              | 3840  | 9.02  * 10**1155 | 3.389 * 10**1152 |
              | 4096  | 1.044 * 10**1233 | 3.679 * 10**1229 |
              +-------+------------------+------------------+

This will hopefully shed some light on what I've always found to be a
fascinating question, which is the unreasonable efficiency of the
general number field sieve.

NIST estimates that a 1024-bit key is about as hard to break as an
80-bit symmetric key, and a 2048-bit key is about as hard to break as a
112-bit key.  So going from 1024-bit to 2048-bit makes it about a
billion times harder to break by brute force.

But when we go from 1024-bit keys to 2048-bit keys, we go from 10**305
possible primes[*] to 10**613 possible primes[**].  There are literally
1,000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000,000,000,000,000,000,000,000,000,
  000,000 more potential primes.  Something like that.  I might be off
by a couple orders of magnitude.  The point is, it's *huge*.

And yet despite that, it's only a billion times harder to break.

You could easily do a Ph.D. in large number theory just looking into why
the GNFS is as curiously effective as it is.  I don't have the math to
give this problem a serious look.  I'm happy just having enough math to
be able to appreciate the magnitude of the problem.  :)

If you want to see the Python code that generated this table, just ask.




[*] Kinda-sorta.  Technically we should subtract out the number of all
1023-bit primes, but honestly, that's almost a rounding error.  Think
about it in base-10.  If I ask you how many 3-digit numbers there are,
you might say 1000.  "No," I'd say, "you have to exclude 2-digit and
1-digit numbers.  There are 100 of those.  There are only 900 3-digit
numbers."  And then you'd slap me upside the head and tell me to stop
being a pedant.  100 is insignificant compared to 1000.  Likewise, the
number of 1023-bit primes can pretty much be ignored when looking for
the number of 1024-bit primes.

[**] Kinda-sorta.  Kind of odd that when we doubled the number we *more
than* doubled the number of primes.  Aren't they supposed to get spread
out more as the numbers get bigger?  This would seem to suggest they got
clustered closer.  This is one of the reasons why I think I got bit by
floating-point error.  Or maybe there's a bug in my code.  Dunno.  Take
your pick.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20150523/110b0662/attachment.sig>