Finding prime factors
- 1977: Inventors of public key cryptography encrypt a challenge
using RSA129, a 129-digit (~400 bit) number N=PQ
- 1994: RSA129 factored over 8 months using 1000 computers
on the Internet, using best known algorithm ("number field sieve")
- Need cracking to take 100 times as long? Make the
key 131 digits (2 digits, 7 bits, 1.5% longer)! (A bit of
an exaggeration, but not much.)
- Builds upon years of work in the theory of computation
Next ...