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