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. $