> From: Yann Forget [mailto:[EMAIL PROTECTED]]
> Could you explain this to me ?
I can try. The text below is deliberately informal in style and far from
mathematically rigorous. The mathematicians on the list will have to
forgive me; those who want a more rigorous explanation should be able to
find one with relative ease.
> I am factoring Fermat numbers with ECM.
> Is this relevant in this case ?
It is relevant for all numbers, but only when ECM produces a composite
factor. To be honest, your chance of finding even one unknown factor of a
Fermat number with ECM is tiny, and your chances of finding two or more *on
the same curve* are somewhere between nil and negligible.
> Paul Leyland said:
> As long as the coefficients of the curve and the starting point are
> recorded, we can re-run exactly the same computation, with the small
primes
> curtailed as in the p-1 case, on the same curve and the number c. It's
> because my software doesn't normally output the curve and starting point
> used that the idea hadn't occurred to me.
Ok, what's happening with ECM is that we are performing arithmetic not with
ordinary integers but with points on an elliptic curve --- a polynomial of
the form y^2 = ax^3+b. (Actually, we are calculating with integers, but in
a complicated manner which corresponds to manipulating points on a
polynomial). The "starting point" I mentioned is a point which lies on the
curve and, with a few special exceptions, it doesn't matter too much which
point is chosen. When the arithmetic is performed modulo a composite
number, there are a finite number of points on the curve. Each different
curve will, in general, have a different number of points. When the number
of points on a particular curve is divisible *only* by primes less than the
first stage limit B1, with perhaps at most one prime larger than B1 but
smaller than the 2nd stage limit B2, ECM will find a corresponding factor.
Usually this factor will be a prime, but occasionally it will be the product
of two or more primes. Each of these primes corresponds to a different
selection of small primes smaller than B1 and, usually, only one will
correspond to the prime larger than B1 and smaller than B2. If you then
repeat the calculation, using exactly the same curve and starting point but
with a reduced set of primes B1, the factor which
corresponds to the omitted primes *won't* be discovered, thereby revealing
the other.
Paul
_
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
