Re: Prime magnitude and keys...a ?

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

Mike Duvos says:
>  > If I have an algorithm that will take any arbitrary RSA key
>  > and produce the private key by a mechanism such as the one
>  > you propose, you are (almost certainly) proposing an
>  > algorithm that will factor arbitrary numbers that are a
>  > product of two primes.
> 
> This is likely true.  However, it does not necessarily follow
> that such an algorithm will be any faster than current methods of
> factoring and might very well be a good deal slower.

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.

> What you seem to be overlooking is that the function Jim
> proposes, which tells the numerical order of two keys from an
> examination of the results of using them, is probably an
> exponential time algorithm itself as a function of keysize.

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.

Perry