Re: A factoring algorithm

Phil Carmody wrote:
> hart_wb@yahoo.com writes:
> > Hi,
> >
> > I have a new factoring algorithm which seems to be very fast with
> > certain kinds of numbers.
> >
> > For example it will factor numbers which are the product of two primes
> > which are both of the "same kind", and fairly close together (say are
> > the same length to within 3 or 4 digits -though that isn't an absolute
> > requirement if you do some fiddling and have a little more time), where
> > by "same kind" I mean that they are both of the form:
> >
> > a*b^n+c where a, b and c are "small"
>
> Such as factoring
>
> 10000000000000000000000000000000000000121000000000000000000070000000000000000000000000000000000000847

Yes, such as this, though the factors are probably getting a little far
apart here for it to be done efficiently.

>
> ?
>
> You just need to find b, and then everything else drops out almost instantly.

It's true, if you rewrite the number in every small base until it has
lots of zeroes, then simply brute force check the million or so
possible factors, you are done. The algorithm I have, does not do that
of course.

>
> > It's a wierd class of numbers to factor, but the algorithm is not
> > contrived.
> >
> > It will also factor general numbers, but is quite slow.
> >
> > It can be sped up for general numbers, but even then it aint that fast.
>
> For general numbers, how does its work factor grow?

Heuristcally O(m^(1/4)) I think, in the most efficient implementation
I've found so far, where m is the number being factored. But I don't
think it competes with SQUFOF in processor cycles (I can never remember
whether SQUFOF is O(m^(1/4)) or O(m^(1/5))). I had hoped for O(m^(1/6))
(for certain naieve reasons) but certainly didn't achieve that yet.

> With the size of the factors?
> With the size of the number being factored?

The latter unfortunately.

>
> > Can anyone think of a serious use for such an algorithm, I mean one
> > that might make use of its special powers? Of course I tried all the
> > RSA prize numbers and a few other most wanted numbers floating around
> > on the web, but obviously I should buy a lottery ticket if I thought I
> > was going to be that lucky. I don't know if they have a caveat that
> > says RSA primes shouldn't be chosen to be of that class, but they
> > certainly should.
>
> Are you sure it actually has special powers, before you try to
> make use of them?

Yes, I suppose I see your point. If there were any numbers that people
were interested in factoring of the form I specify, one wouldn't need a
special algorithm to factor them.

In fact perhaps it is best used as a general algorithm, since it will
factor some numbers extremely quickly. Perhaps it could be used in
conjunction with pollard-rho and SQUFOF for a limited number of cycles,
in finding factors of small numbers, where it can often find factors
very quickly, though not always.

Anyhow, I need to do some more fiddling to see what can be done. For
now you are right.That isn't a useful algorithm and only has
theoretical interest.

Bill.

>
> Phil
> --
> What is it: is man only a blunder of God, or God only a blunder of man?
> -- Friedrich Nietzsche (1844-1900), The Twilight of the Gods
Received on Tue Jan 17 16:49:04 2006