The keys to the kingdom

RSA Conference USA 2011RSA 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 2512 / log(2512) ≈ 3.8 × 10151 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 × 10110 years on average to find the answer; not even close to realistic.

05/31/12
by mathowie

Highlighting the best bits from the MetaFilter universe

MetaFilter started as a community weblog in 1999, later added question and answers, then music by members, jobs, projects by members, a podcast, and finally an area dedicated to meetups.

View Best Of Archive

feed  Subscribe to the Feed

twitter  Follow at Twitter

tumblr  Follow at Tumblr

facebook  Like at Facebook

Contributors

profile

Matt Haughey

mathowie

profile

taz

taz

profile

Josh Millard

cortex