# [RC5] possible third project...

Ryan Malayter rmalayter at bai.org
Mon Jul 30 11:50:01 EDT 2001

```Hmm... I guess I don't remember those algorithms classes to well.

The running time of the GNFS is:
O( exp(c*ln(n)^1/3 * ln(ln(n))^2/3 ) )

I assumed N represented the size of the input the number field - all
integers to be tested as factors, which would be 2^64 times as large the
field for RSA-512. Is N calculated differently?

Upon reflection, N should probably be the number of primes less than the
square root of the factorization target. In this were the case, N would be
~2^32 times as large for RSA-576. Plugging this into the complexity formula
above gives ~100000 the run time of RSA-512.

I didn't look at the algorithm in detail, so I guess I just don't know
enough to calculate N. And since Differential Equations II was as far as I
went as an engineer in college, maybe I couldn't calculate N if I knew the
algorithm backwards and forwards ;-).

-ryan-

-----Original Message-----
From: Jeff Gilchrist [mailto:jeffg at cips.ca]
Sent: Saturday, July 28, 2001 8:48 AM
To: rc5 at lists.distributed.net
Cc: rmalayter at bai.org
Subject: RE: [RC5] possible third project...

Hi Ryan,

I am one of those researchers who cracked (more precisely, factored)
RSA-512.
We also more recently factored a 773bit (or 233 digit) Cunningham number
(2^773+1) using the SNFS.

I'm not sure how you calculated that doing RSA-576 would be 13 million times

harder than RSA-512.  Talking with my colleagues the best guess is about 11
times harder, yes only eleven.

The other major problem with sieving is that it requires a large amount of
RAM.  Clients would probably need a minimum of 64MB of RAM just for the
d.net
client, more is better.

As for the post-sieving step that usually takes place on a powerful
computer,
that shouldn't be a problem for this contest.  Several people in the group
that
did RSA-512 are working on parallelizing this step.

As for the suggestion from Jonathan about brute forcing the factors, I think

you will find that would take an infeasible amount of time.

Regards,
Jeff.

Quoting Ryan Malayter <rmalayter at bai.org>:

> 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-
--
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

```