Computational Complexity

[mpd@netcom.com (Mike Duvos)]

Perry E. Metzger writes:

 > Ahem. He was proposing a mechanism that will work in log(n)
 > time. All current known methods are subexponential. As you
 > SHOULD know, a log function will eventually be smaller than
 > a subexponential one if you only let N grow large enough.
 > This is baby complexity theory. I find it astonishing that I
 > should even have to mention it.

As I read it, he simply asked (and quite nicely at that) if such
a algorithm might exist, and asked if there were any references
to it in the literature.  Now clearly he was hoping that such a
mechanism might offer the opportunity to binary search the key
space efficiently and perhaps those hopes were misplaced, but I
don't think the idea was so off the wall as to be deserving of
the ridicule you heaped upon it.  Far weirder things have been
proposed on this list.

 > Thats not what he was proposing. Obviously one can build
 > such an algorithm given a factoring algorithm, and we know
 > of exponential factoring algorithms. That wasn't the idea.
 > His notion was that there might be a CHEAP algorithm to do
 > this.

I think the key word here is "might."  Hope springs eternal, even
in cryptology. :)

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $