From: Jack Lloyd (lloyd@randombit.net)
Date: Mon Aug 27 2007 - 08:46:55 MDT
On Sun, Aug 26, 2007 at 08:53:44PM -0700, Eliezer S. Yudkowsky wrote:
> Heard from a friend: "I recall a comment from D-Wave Systems that a
> 1974 era computer running 2007 algorithms would beat a modern computer
> running 1974 algorithms." Topic was decryption / factorization.
Pollard didn't invent his rho algorithm until 1975, so there
essentially was no decent factorization method at the time (and the
rho algorithm, while better than previous methods, is exponential with
the size of the input). The number field sieve (1994) and later
variations have sub-exponential running times which alone probably
make up for three decades of process improvements.
A more recent example is RSA-129 versus RSA-140:
RSA-129, 1994: quadratic sieve algorithm, estimated 5000 MIPS years
http://www.mit.edu:8001/people/warlord/RSA129-announce.txt
RSA-140: 1999: number field sieve algorithm, estimated 2000 MIPS years
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind9902&L=nmbrthry&P=302
Both required about 4 gigabytes of RAM for the matrix sieving, which
would be difficult and slow but probably doable on large machine of
1974.
-Jack
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:58 MDT