### Re: Mersenne: ECM Question...

```
Alexander Kruppa wrote:

gp_p(x) | go_p, and p+1-sqrt(p) = go_p = p+1+sqrt(p) . Since go_p(x)

Correction: I have taken the limits above from my memory which has once
again proved itself untrustworthy. The correct limits are
p+1-2*sqrt(p)  go_p = p+1+2*sqrt(p) , a theorem by Haase, which I
found in O. Forster, Algorithmische Zahlentheorie.

Ciao,
Alex.
_
Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

```

### Re: Mersenne: ECM Question...

```
Steve Phipps wrote:

While we're on the subject, can someone explain how to derive the group
order for factors found using ECM? I've been carrying out ECM on an old PC
for almost a year now, and I'd like to be able to derive, and factorise,
the group orders for the factors that I've found.

I've been making an effort to understand the maths, and I'm getting there
slowly, but I've found nothing yet that explains how to derive the group
orders. If my understanding is correct, you would need to know the
equations used by mprime to derive the co-ordinates of the starting point
for each curve.

Anyway, if someone could explain how to derive the group order, or point
me in the right direction, I'd be very grateful.

Regards,
Steve

I'm by no means an expert on ECM, but let me try..

There seems to be a formula to compute the order of an elliptic curve
over Z/p*Z, p prime, but that formula is afaik rather complicated to
compute.
What you can do when you want the order of a successful ECM curve is
this:
p is the factor of N that was found by the curve, go_p is the order of
the curve and go_p(x) is the order of x in that curve.
If a!=0 but a*q=0, q prime, then q is the group order of a and a factor
of the order of the group. (0 is the neutral element here).
You can run the sucessful ECM curve normally, but test for a factor
after every multiplication with a prime q and see if the factor p is now
found - if so, then q is a factor of the group order. Remember the q's
and restart the curve, but multipliying the initial point x with all the
q's to find smaller factors of the group order.
A very informal algorithm might look like this:

known_go = 1
restart:
set x to the initial point
x = x*known_go
if gcd(x_z, N)  1 print known_go, exit
for all primes and prime powers q below bound B
x = x * q
if gcd(x_z, N)  1 then known_go *= q, goto restart

This will reveal the order of the initial point x. But we want the order
of the group (go_p), not that of x (go_p(x)). However we know that that
gp_p(x) | go_p, and p+1-sqrt(p) = go_p = p+1+sqrt(p) . Since go_p(x)
is usually much larger than 2*sqrt(p), the second equation has only one
solution in integer k if you replace go_p by k*go_p(x). Find the correct
k, i.e. by trunc((p+1+sqrt(p)) / go_p(x)), and k*go_p(x) is the group
order you wanted.

I once tried this with the mprime ecm code and actually were able to
verify the known group orders of some factors, but I never really
cleaned up and debugged the code - for example, you cant stop and
restart the go run, and after the run all the internal variables are
probably not restored cleanly enough to continue with regular curves,
etc. If there is interest in this code, I'll try to clean it up enough
to make it more or less suitable for public display - provided George
has no objection to spreading a modified version of his code.

Ciao,
Alex.
_
Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

```

### Re: Mersenne: ECM Question...

```
While we're on the subject, can someone explain how to derive the group
order for factors found using ECM? I've been carrying out ECM on an old PC
for almost a year now, and I'd like to be able to derive, and factorise,
the group orders for the factors that I've found.

I've been making an effort to understand the maths, and I'm getting there
slowly, but I've found nothing yet that explains how to derive the group
orders. If my understanding is correct, you would need to know the
equations used by mprime to derive the co-ordinates of the starting point
for each curve.

Anyway, if someone could explain how to derive the group order, or point
me in the right direction, I'd be very grateful.

Regards,
Steve

If the sigma is the same, then a curve with B1=25 will find any
factor that a curve with B1=5 finds.
When you run 700 random curves at B1=25, you might theoretically
miss a factor that someone else finds with B1=5, if he gets a lucky
sigma so that the group order is very smooth. But in general, using the
same number of curves, the higher bound should find all the factors that
the lower bound can find.
But dont be tempted into running only a few curves at very high bounds.
The strength of ECM is that you can try curves with different group
orders until a sufficiently smooth one comes along. So skipping bound
levels is usually not a good idea unless you have reason to believe the
the number unter attack has only large factors which call for a higher
bound.

_
Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

```

### Re: Mersenne: ECM Question...

```
Eric Hahn wrote:

If a person runs an ECM test using a B1 of 250,000 with 700
curves (for up to 30 digits), will they also find any factors
that they would have found if they had used a B1 of 50,000 with
300 curves (for up to 25 digits) ?!?

Eric

If the sigma is the same, then a curve with B1=25 will find any
factor that a curve with B1=5 finds.
When you run 700 random curves at B1=25, you might theoretically
miss a factor that someone else finds with B1=5, if he gets a lucky
sigma so that the group order is very smooth. But in general, using the
same number of curves, the higher bound should find all the factors that
the lower bound can find.
But dont be tempted into running only a few curves at very high bounds.
The strength of ECM is that you can try curves with different group
orders until a sufficiently smooth one comes along. So skipping bound
levels is usually not a good idea unless you have reason to believe the
the number unter attack has only large factors which call for a higher
bound.

Ciao,
Alex.
_
Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

```

### Re: Mersenne: ECM question

```
Hi all,

I have a different question concerning P-1 and ECM.
Some time ago I asked which power to put small primes
into when multiplying them into E ( factor = gcd(a^E-1,N) ).

Paul Leyland, I believe, replied that the power for prime p should
be trunc( ln(B1) / ln(p) ) ( log(B1) with base p ),
where B1 is the bound up to which we put primes into E.

But what if there is a stage 2 with a higher bound B2?
Should it be trunc( ln(B2) / ln(p) ) then? Or still the stage 1 bound?
Franz-Dieter Berger mentiones on page 40f that his experience
shows that it is better to use the stage 2 bound.

Any opinion from the factoring gurus here on the list?

Ciao,
Alex.

Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm

```

### RE: Mersenne: ECM question

```
The function being minimized, namely

probability of finding a 50-digit factor on one curve
-
time per curve

is flat near its minimum.  Implementation and platform differences
can obviously affect the denominator (time per curve).
The stage-2 strategy affects the numerator.  The two optimal B1's
are close enough to be considered the same.

Umm.   I think you want to maximize the probability.

Minimizing it is easy.

Paul

Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm

```

### RE: Mersenne: ECM question

```
At Paul Zimmerman's ECM page,
http://www.loria.fr/~zimmerma/records/ecmnet.html
the optimal B1 value listed for finding 50-digit factors is
4300, but
George's ECM factoring page uses 4400 for the same
purpose. Is one of
them wrong, or is there a reason for the difference?

No, neither is "wrong", for at least two reasons.

First, ECM is a probabalistic algorithm.  Each run chooses a random elliptic
curve and has a certain chance to find a factor of a particular size.   When
enough curves have been run, there is particular probability of finding a
factor of that size, assuming that one exists.  If one choose 50% as the
desired probability, the number of curves required will obviously be fewer
than if one chooses 60%, say.  A similar choice can be made for trading off
B1 value against probability, as long as the trade isn't pushed too far.

Another reason is that the B1 value is only one quantity of importance.
Even if the probability mentioned above is fixed, the optimal number of
curves depends on the value of B2.  Different implementations of ECM (or
even different runs of the same implementation) are free to choose different
values of B2 for a given B1.

A non-reason, but still of interest, is that the maximum in the probability
agains B1 curve is really rather flat, and it doesn't matter too much if
parameters are chosen which are not strictly optimum.

Paul

Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm

```