[RC5] RSA 576 broken

Ben Wilhelm zorbathut at uswest.net
Fri Apr 30 17:57:19 EDT 2004


Remember that complexity theory doesn't say anything about the constant
factor - only how much slower it gets as n increases. In complexity theory,
the area of a square is O( n^2 ), but the area of the largest triangle
inscribed in that square is also O( n^2 ), despite the fact that the
triangle is obviously half as large.

It's also worth pointing out that they're comparing that painful-to-write
equation (at
http://en.wikipedia.org/wiki/Integer_factorization#Current_state_of_the_art )
to O( e^n ) - the GNFS equation ends up being 6.969986807462673e+023, while
O( e^n ) comes out to 1.42436592743065e+250. Of course, as mentioned before,
both of those are totally meaningless numbers :)

-Ben

>
> Hm.
>
> Calculating O for n=2^576 gives about 1.24e21, or 1.60e12 per second
> per computer, which seems a little large (the O given in Wikipedia is
> much, much larger, strangely).
>
> The scary part? Factoring a 1024-bit number should only take about a
> million times longer.
>
> - Purr
>
> _______________________________________________
> rc5 mailing list
> rc5 at lists.distributed.net
> http://lists.distributed.net/mailman/listinfo/rc5
>



More information about the rc5 mailing list