[RC5] possible third project...

Jeff Gilchrist jeffg at cips.ca
Sat Jul 28 10:48:27 EDT 2001


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



More information about the rc5 mailing list