Hi folks
> 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.
> 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)
> 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?
I can give a reasonably informed answer to this, having tried it myself. To
use Fermat's method directly on kN in order to factor N, unless you are very
lucky, is no improvement. In the 2^727-1 case, as pointed out, since you
know the form of the factors, it's sufficient to try a=727x+1, for all a
above sqrt(N), to check a^2-N is a perfect square. To preserve this, make
the factor you multiply by a product of factors of the form 1454k+1 - all
the factors of the product are still of this form.
Do we win, or do we lose? Let's suppose that our composite has precisely two
prime factors, and thus direct application of Fermat will uncover only one
non-trivial solution from which we can derive the factor values. If what we
multiply by has k distinct factors, then there are now 2^k useful
solutions - but the number of values of a that we need to try has increased
by more than that factor. In all likelihood, it would take longer...
But don't despair. Since all we have to check for is "a^2-N is a perfect
square", it's easy just to inspect this value modulo many small primes and
sieve out quadratic non-residues. With a few lookup tables, it's easy to
trial-factor at 10^9, even 10^12, values of a per CPU-second. Even so, for a
219-digit number like 2^727-1, and even assuming there's no factor below 40
or so digits, you'd still need 10^60 or more CPU-seconds to spare. (OK if
you've got a universe with nothing else to do).
Unsurprisingly, the method needs a bit of control to be realizable - which
is what the continued fraction method achieves. Each iteration finds a
(relatively) small square modulo N (at worst sqrt(N) in absolute value),
which, after striking out square factors, making sensible choices of which
to store, and judicious combinations, you hope to eventually find
non-trivial a^2=b^2 mod N. Still need a lot of luck, though, and the steps
are now non-trivial...
Chris Nash
Lexington KY
UNITED STATES
==================================================
Still a co-discoverer of the largest known *non*-Mersenne prime
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
