Re: Prime magnitude and keys...a ?

["Perry E. Metzger" <perry@imsi.com>]

I said:
> > Of course you haven't seen such a thing. If factoring RSA keys
> > requires exponential time, such an algorithm is obviously not
> > possible. Were it possible, you could factor in time proportional to
> > the the number of bits in the key. Anyone who had such a function
> > would either be famous or wouldn't be talking.

Jim choate says:
> How about some evidence on it? I see no reason to compare taking a key
> and determining if it is too large or too small as being necessarily
> equivalent to factoring a large number.

Its called "binary search". You were supposed to learn it in your
intro to computer science class.

Lets play the guessing game, shall we? Its much like twenty questions,
only that just works for twenty bit things or less. We know that we
have a big number. If you give me a function that tells me one bit
(greater or not greater) for every guess, I can get a bit of the
number. After a short time, I'll know the number -- the time is
exactly the number of bits in the number (that is, the log base 2 of
the number.)

Perry