On 14 Feb 2002, at 20:00, [EMAIL PROTECTED] wrote: > Rich Schroeppel <[EMAIL PROTECTED]> writes: > > <<< > The cost analysis of trial factoring by GCDs of 2^P-1 with the > product of many small candidate divisors ignores an important > optimization: All the candidates can be multiplied together > mod 2^P-1, and ONLY ONE GCD NEEDS TO BE DONE. The major cost is > probably the multiplications. Reduction mod 2^P-1 is particularly > fast, but the same principle applies to random ultra-large targets.
Umm. Can someone please reassure me that we're not re-inventing P-1 stage 1? 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. In that time you can try ~ 10^9 63-bit factors, even ignoring those which fall through the sieve. Please don't let my scepticism put you off; you're quite right to say that advances only come from thinking the unthinkable; but, if there is significant mileage in this idea (and it isn't a straight rehash of P-1), then (in the words of HHGG) surprise will no longer be adequate, and I will be forced to turn to astonishment. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
