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.) Here is a link detailing pentium clock cycles for various instructions: http://orakel.tihlde.org/kurs/3d/download/PENTIUM.TXT You'll see that the instructions for loading 8-bit values and performing an XOR, shift and compare is pretty low (<25 clock cycles on paper anyway). The clock cycles for an average multiplication is in the tens-to-hundreds of clock cycles. It's a bit more difficult to calculate the clock cycles for larger values, but in principle this should engage much fewer clock cycles than traditional factoring techniques. 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?? I've contacted the amateur mathematician to see if we can obtain more info. phillip -----Original Message----- From: owner-cypherpunks@Algebra.COM [mailto:owner-cypherpunks@Algebra.COM]On Behalf Of Alan Olsen Sent: Monday, February 05, 2001 4:43 PM To: Warren Piece Cc: cypherpunks@cyberpass.net Subject: Re: fast way to decode RSA encryption On Mon, 5 Feb 2001, Warren Piece wrote:

anyone else seen this claim? http://www.mb.com.ph/INFO/2001-02/IT020201.asp

Yep. Slashdot has a quote from Ron Rivest on why it is not a break or a big deal. (The method works, but it is *slower* than factoring.) http://slashdot.org/article.pl?sid=01/02/05/1911258&mode=flat alan@ctrl-alt-del.com | Note to AOL users: for a quick shortcut to reply Alan Olsen | to my mail, just hit the ctrl, alt and del keys. "In the future, everything will have its 15 minutes of blame."

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