[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



More information about the rc5 mailing list