# [RC5] possible third project...

Jonathan Smith jsmith at cygnacom.com
Fri Jul 27 16:50:45 EDT 2001

```Of course we could not use the general number field sieve.  We could just
brute force try the "keyspace", just like we are doing for rc5-64.  Based on
RSA's web site we know that each number has only two factors.

"Each number is the product of two large primes, similar to the
modulus of an RSA key pair. "

By emailing RSA using the supplied contact in their factoring challenge faq
http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html
we can get the code used to create the random numbers, this should allow us
to
determine the approximate sizes of the numbers involved, because I image
that the software sets boundary conditions to prevent the factors from being
of hugely different sizes.

Then just hand out ranges of numbers inside this boundary to clients and let
them
try dividing the contest number by each number in the range. **
If the result was an integer then you are done and have found both factors.

This has the advantage of being ridiculously parallel, with very low
bandwidth
requirements making it ideal for a distributed.net project.  It eliminates
the
final sieve required by the general number field sieve algorithm and with it

the huge singe machine cpu and memory requirements.

So we don't have to use the best scheme, we could just try throwing enough
computers
at the problem to do it the hard way.

Jonathan Smith
--
** Clearly their are various optimizations possible, since we know that the
factors are prime
at the simplest without bothering to compute all the primes in the range we
could immediately
discard all the even numbers, or have the clients work out primes, etc.

-----Original Message-----
From: Ryan Malayter [mailto:rmalayter at bai.org]
Sent: Friday, July 27, 2001 12:31 PM
To: 'rc5 at lists.distributed.net'
Subject: RE: [RC5] possible third project...

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.distributed.net/pipermail/rc5/attachments/20010727/15b3ee12/attachment-0001.htm
```