On 14 Jun 00, at 4:49, Paul Leyland wrote:
> It's a pity that a similar procedure isn't known for ECM, or at least not
> known to me.
Isn't the point that ECM finds numerically small factors much more
easily than it finds numerically large factors? Therefore, if a
"reasonable" amount of trial factoring has been done, it's very
unlikely that a previously undiscovered factor will be found
directly, unless it's prime.
It's even less likely that this will happen provided that sufficient
runs with smaller B-limits are done before going on to larger B-
limits.
Of course, if we find a prime factor which is less than the cube root
of the number we're working with, the cofactor (found indirectly by
dividing the number by the new factor) may still be composite. Using
ECM, the cofactor may in fact be composite even if the new prime
factor is a bit bigger than the cube root, for reasons connected with
the probabilistic way in which ECM works.
One possible method for dealing with numbers with existing known
factors is to keep the known factors in a database and, when the GCD
is found to be greater than 1, dividing the result of the GCD by as
many of the known factors as possible until the result becomes 1 (in
which case only already known factors have been found) or no more
known factors are available (in which case we found a new one). This
would work equally well for P-1 and ECM.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
