[RC5] possible third project...

Ryan Malayter rmalayter at bai.org
Mon Jul 30 11:08:14 EDT 2001


http://www.frenchfries.net/paul/factoring/theory/nfs.html

The complexity of the algorithm is:
O( exp(c*ln(N)^1/3 * ln(ln(N))^2/3 ) )

Where c ~1.9223

Since N for RSA-576 is 2^64 times larger than N for RSA-512, it should take
~13 million times longer to run on the same hardware.



-----Original Message-----
From: Dennis Lubert [mailto:plasmahh at gmx.net] 
Sent: Friday, July 27, 2001 4:35 PM
To: rc5 at lists.distributed.net
Subject: RE: [RC5] possible third project...


At 11:31 27.07.01 -0500, you wrote:
>Given to the running time of the General Number Field Sieve, RSA-576

Do u have ne information about how this Number Field Sieve algorhitm works ?

>factorization should take about 13 million times the computer resources 
>than RSA-512 factorization took.
>
>We know what the researches who cracked RSA-512 used... The question 
>is, do we have enough computer power (comparatively) to make the 
>sieving operation a feasible project? And will those results even be 
>usable, given that the back-end, single-computer operation will be many 
>times larger - perhaps too large for even the biggest supercomputers?
>
>         -ryan-
>
>-----Original Message-----
>From: Greg Wooledge [mailto:greg at wooledge.org]
>Sent: Thursday, July 26, 2001 5:08 PM
>To: rc5 at lists.distributed.net
>Subject: Re: [RC5] possible third project...
>
>
>Mathieu Gilbert (wilbrod at videotron.ca) wrote:
>
> > Nice ... that would be a great project, easy to understand and to 
> > explain(so you can get newbie installing the client even if they 
> > don't know anything about computers/math/.. not too long to complete 
> > ..
>
>Hah!  Factoring even the lowest of the current RSA factoring challenges 
>is definitely non-trivial.  The fastest know general factoring 
>algorithm (the Number Field Sieve) can be parallelized in the first 
>stage, but then the results of the first stage have to be fed to a 
>single large computer for a few weeks of crunching.
>
>(The RSA-155 challenge, which involved factoring a 155-decimal-digit 
>number, required several weeks of processing on a 4-CPU Alpha box with 
>4 GB of RAM.)
>
> > Moreover dnet and someone could make some easy money.
>
>Believe me, any such money would be *earned*. :)
>
>--
>Greg Wooledge                  |   "Truth belongs to everybody."
>greg at wooledge.org              |    - The Red Hot Chili Peppers
>http://wooledge.org/~greg/     |
>--
>To unsubscribe, send 'unsubscribe rc5' to 
>majordomo at lists.distributed.net rc5-digest subscribers replace rc5 with 
>rc5-digest

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list