[RC5] possible third project...

Basil A. Daoust basildaoust at home.com
Fri Jul 27 17:51:07 EDT 2001

The RSA Factoring challenge is an effort, sponsored by RSA Laboratories, to learn
about the actual difficulty of factoring large numbers of the type used in RSA keys.
A set of eight challenge numbers, ranging in size from 576 bits to 2048 bits is
posted here. Each number is the __product_of_two_large_primes__, similar to the
modulus of an RSA key pair. 

I suppose I should go read about this Field Sieve process but it sounds like a
general solution to factoring and if I understood the RSA challenge the number is a
factor of just TWO prime numbers.  Does it make sense to use a sieze to find a bunch
of factors for something that has only 2?  OR as I suspect I just don't get it.

Would it not be easier just to see if each prime up to the squareroot of the number
would divide into the number and the result be a prime?  Since calculating the primes
can be easily distributed as per the description it seems that groups of primes could
be distributed for testing against the RSA #.


Ryan Malayter wrote:
> Given to the running time of the General Number Field Sieve, RSA-576
> 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

More information about the rc5 mailing list