Prime magnitude and keys...a ?

[Perry E. Metzger]

Jim choate says:
> What I am looking at is a way to do binary searches in the key space w/ a 
> function that would look at a test key and the result of running RSA on 
> it and then tell me the relative magnitude between the real key and the
> test key. 

And you think no one would have noticed such a thing before.

I can pretty much hint to you that such a thing can't really be done
in log base 2 of n time in the sense that I believe I can prove that
any algorithm that did that would have to involve none of the basic
four arithmetic operations on the numbers in question. (Algorithms
involving no arithmetic on the numbers are still possible, but
intuitively quite unlikely.)

Perry