> From: Brian J. Beesley [mailto:[EMAIL PROTECTED]]
> 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.
Yes and no. ECM has behaviour very similar to P-1 and P+1 (which is not too
surprising, as they are all essentially the same algorithm) and does indeed
tend to find small factors easier than large ones. However, if there are
two small factors, each of which are smooth in the appropriate sense, they
will be found together.
> 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.
Not always true. I recently was running ECM with very small limits to pick
up factors in the 6 - 10 digits range (yes, I know ECM isn't the optimal
algorithm for factors this small but my ECM program is available and easy to
use) and found a 39 digit composite factor! It subsequently turned out to
have four distinct prime factors.
Today I found this number 3756482676803749223044867243823 with ECM and
B1=10,000. It has two factors, each of 16 digits, which could *not* have
been found by trial division in any reasonable time.
Paul
>
> 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
