Re: A factoring algorithm

b needs to be the same, the others may differ, but you don't want the
n's to vary by too much unless you have a lot of time on your hands,
though variations of the algorithm get around this to a certain extent.
I haven't worried too much about that though, since it is my impression
that RSA moduli are often picked with the primes within 3 or 4 digits
of each other in length.

You are indeed correct in your analysis though. It is an insignificant
fraction in the naieve form of the algorithm. I simply hadn't
considered this. I am not a crypto expert, which is why I posted here
for comments. I don't even spend a huge number of cycles coming up with
algorithms normally. I am a pure mathematician in the generic case.

I won't be posting any information about the other versions for quite
some time, if at all, as they need some serious coding to even make
them approach their supposed asymptotic efficiency, and I haven't that
much time. I'm already tied up working on a quadratic sieve
implementation anyway, in my spare time, and that is faring relatively
well.

I wouldn't even like to guess how the other versions of my algorithm
perform (except to say that in the worst case scenario one of them will
take m^(1/4) iterations, and in another version it can be made
subexponential, but without, to date, apparent benefits over the
continued fraction algorithm, say, i.e. useless).

I'm also not willing to apply for a grant of time on a supercomputer,
or tie up the local cluster, checking, at this point.

Till next time.

Bill.
Received on Tue Jan 17 16:49:09 2006