Lucky's 1024-bit post

[Anonymous]

On Tue, 30 Apr 2002 at 17:36:29 -0700, Wei Dai wrote:
> On Wed, May 01, 2002 at 01:37:09AM +0200, Anonymous wrote:
> > For about $200 you can buy a 1000 MIPS CPU, and the memory needed for
> > sieving is probably another couple of hundred dollars.  So call it $500
> > to get a computer that can sieve 1000 MIPS years in a year.
>
> You need a lot more than a couple of hundred dollars for the memory, 
> because you'll need 125 GB per machine. See Robert Silverman's post at 
> http://groups.google.com/groups?hl=en&selm=8626nu%24e5g%241%40nnrp1.deja.com&prev=/groups%3Fq%3D1024%2Bsieve%2Bmemory%26start%3D20%26hl%3Den%26scoring%3Dd%26selm%3D8626nu%2524e5g%25241%2540nnrp1.deja.com%26rnum%3D21
>
> According to pricewatch.com, 128MB costs $14, so each of your sieving 
> machines would cost about $14000 instead of $500.

Silverman's comment makes sense; the memory needed is probably
proportional to the size of the factor base, and going from 512 to 1024
bits would plausibly increase the factor base size by at least 11 bits,
corresponding to a memory increase of a factor of ~ 2500 as he says.
If the 512 bit factorization used 50 MB per node for the sieving then
that would require extreme amounts of per node memory for 1024 bits.

But how about using disk space instead of RAM for most of this?  Seems
like a sieve algorithm could have relatively linear and predictable memory
access patterns.  With a custom read-ahead DMA interface to the disk it
might be possible to run at high speed using only a fraction of the RAM,
acting as a disk buffer.  A 125 GB disk costs a few hundred dollars,
so that might bring the node cost back down to the $1000 range.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com