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, [EMAIL PROTECTED]
PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
