At 12:17 AM 2/6/01 -0500, Phillip H. Zakas wrote:
I spent a little bit of time studying this approach. I know Rivest is dismissing it, but from a computational perspective it's more efficient in terms of clock cycles than trying to factor a number using multiplication/division (at least using the Pentium chip.)
... If this isn't a true crack as Rivest claims, it's at least a (computationally) faster factoring technique. Perhaps this is the way to more quickly win the next DES-cracking challenge. Is my analysis off-base??
Yes, your analysis is way off base. The reason is that there are much better algorithms for factoring - a factor of 10 difference in the number of clock cycles per step is rapidly dwarfed by an algorithm that takes far fewer steps. If you look at Schneier's book, there's a discussion of factoring algorithms - Quadratic Sieve algorithms are good for fewer that 120-150 digits, and above that there are algorithms like the Number Field Sieve and its variants with run times of e**( (ln n)**(1/3) * (ln (ln n)**(2/3)) ) which is a lot fewer than trial division. Check out Odlyzko's work on solutions to the discrete log problem. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639