Best Of MetaFilter

RSA Conference USA 2011 by Riebart (cc by)

In a recent thread discussing an introduction to cryptography, member Rhomboid explains why a seemingly simple problem at the root of all internet security, figuring out the two prime numbers multiplied by each other to get a 309-digit number (that would unlock the ultimate root certificate) is so incredibly difficult:

Actually doing this is quite another matter. By the prime number theorem, we have about 2⁵¹² / log(2⁵¹²) ≈ 3.8 × 10¹⁵¹ prime divisors to test. Suppose we had a computer that can perform such a test division in a single clock cycle, and say that it runs at 100 GHz. Say that we have 100 billion such computers on the planet, and heck, say we have 100 billion such planets. You're still looking at ≈ 6 × 10¹¹⁰ years on average to find the answer; not even close to realistic.