On 14 Jul 99, at 7:59, Paul Leyland wrote, in reply to
my earlier message:
> > Actually Fermat's Method is extraordinarily efficient at finding a
> > factorization n = a * b when (a - b) is small. It's also easy to
> > code, needs very little storage and (once initialized) requires only
> > relatively low-precision arithmetic, therefore making the attempt
> > fast (per iteration).
>
> All of this is completely true, as long as the concept "small" is well
> understood.
>
> Fermat's method is excellent if (a-b) is about sqrt(a) or
> sqrt(sqrt(N)). If it is much larger than this, Fermat's method is
> hopelessly slow. In a "typical case", Fermat's method is slower than
> trial division!
I think you mean we want (a-b) to be _much_ smaller than sqrt(a) if
Fermat's method is going to succeed reasonably quickly. However, ...
Suppose we take a number which is proving troublesome to factorize,
e.g. 2^727-1. Factors of this number are going to be of the form
1454k+1. The number is 219 decimal digits long; we are fairly sure,
from work expended in ECM, that there are no factors much less than
45 digits long.
Suppose we multiply 2^727-1 by 100!. The reason for doing this is
that this just about guarantees that there is some combination of
factors a, b such that (a-b) << sqrt(a). Therefore we should be able
to use Fermat's method (or anything else which might be better) and
get a factorization in a reasonable time. We also know that none the
factors of 2^727-1 are < 100, so we can then reduce the factors found
by dividing out of them all the primes < 100. What we're left with
must surely be the factorization of 2^727-1 (though the remaining
factors might possibly still be composite).
Now I'm not saying that the effort involved is trivial - I'm sure a
run length of some hours, days or weeks would be neccessary. Also,
I'd be very surprised indeed if I'm the first to suggest a trick like
this, but, is it worth while starting to code this method? The point
is that it's going to take a fair number of CPU years to complete ECM
testing on 2^727-1 to the point where we're reasonably sure that
there are no factors < 10^50; for all we know, there might be only 2
factors each over 100 digits long, in which case ECM is almost
certain to fail, unless _much_ faster hardware comes along.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
