17 Dec
2003
17 Dec
'03
11:17 p.m.
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