Mersenne: Re: Trial Factoring: Back to the math

[EWMAYER]

Brian Beesley writes:

>Umm. Can someone please reassure me that we're not re-inventing
>P-1 stage 1?

The algorithm under discussion does share some superficial
features with p-1, in that we do a bunch of a big-integer
modular multiplies followed by a gcd to extract any factors.
But in fact we have complete control over the factors that
will be found, by way of the candidates we throw into the
accumulated product. So it really is equivalent to sieve-based
trial factoring, the difference being in the way we test the
candidates.

>The other point here is that the GCD is _expensive_. On a 1GHz
>P3 or Athlon the GCD at the end of P-1 on exponent ~10^7 takes ~
>10 minutes.

Ah, but that's (as Rich Schroeppel pointed out) the beauty of
modular arithmetic. If we only need to do a single gcd, who cares
if it takes ten minutes or even a few hours?

If it became clear that we could implement this algorithm and
have it run within factor of no more than 3-4 times slower than
one-factor-at-a-time sieving for factors <= 64 bits, it would be
very promising indeed, since it suffers no large performance
hit for factor candidates above 64 bits. And it would allow
machines with poor integer multiply (e.g. the Sparc family)
to join in the factoring work, since most of the work could
use floating-point arithmetic, irrespective of the size of
the factors.

-Ernst