[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