ECM on Mersenne numbers with prime exponents

[biwema]

An elliptic curve is successful, if the group order (p - 1 + sigma) of a given prime factor is smooth.

When looking for p-1 on mersenne numbers, we take advantage of the property, that a factor has the form p = (2k*exp) + 1. so exp can be taken into the group order of the p-1 factor.

Is it possible to choose the sigma of the ECM group order as multiple of 2*exp?
Sigma = 2*k*exp.
In that case that will give some extra digits and increase the efficiency.

Does that theoretically work, and is that optimisation already included in prime95?

[xilman]

Originally Posted by biwema

An elliptic curve is successful, if the group order (p - 1 + sigma) of a given prime factor is smooth.

When looking for p-1 on mersenne numbers, we take advantage of the property, that a factor has the form p = (2k*exp) + 1. so exp can be taken into the group order of the p-1 factor.

Is it possible to choose the sigma of the ECM group order as multiple of 2*exp?
Sigma = 2*k*exp.
In that case that will give some extra digits and increase the efficiency.

Does that theoretically work, and is that optimisation already included in prime95?

Unfortunately not.

Unfortunately, because the value "sigma" is used for two quite different quantities and the value used to choose the term is not the same one as appears in the formula for the group order.

Paul

[biwema]

I know that there are many different definitions of sigma.

I try to change my question then:

Is it possible to choose the coeffizients of the ECM group order as multiple of 2*exp?
That we choose sigma, that the group order is

p - 1 + 2*exp.

which has a higher probability of being smooth?

I don't know how the relation between the group order and sigma (in prime95 or gmpecm) is, but if jus needs to be chosen that the group order has that form.

[R.D. Silverman]

Originally Posted by biwema

I know that there are many different definitions of sigma.

I try to change my question then:

Is it possible to choose the coeffizients of the ECM group order as multiple of 2*exp?
That we choose sigma, that the group order is

p - 1 + 2*exp.

which has a higher probability of being smooth?

I don't know how the relation between the group order and sigma (in prime95 or gmpecm) is, but if jus needs to be chosen that the group order has that form.

I know what you are trying to ask, but what you wrote is not what you want.
You want to choose coefficients so that the group order over Z/pZ is a priori divisible by 2*exp.

It is not possible unless exp = 2,3,4,6, or 8. We can construct curves that
explicity have points of order 4,6,8,12, or 16.

Read P. Montgomery's 1987 paper for a full explanation.

[dsouza123]

I noticed when entering the values for F14 using M32768 with ECM on Prime95,
there is a checkbox with the label Factor 2^N + 1.

My understanding is the M32768 as 2^32768-1 which covers F14's 2^16384+1 so it was left unchecked.

Is this correct ( sure hope so ) ?

Is there any use for the checkbox with ECM and Fermat numbers ?

[dsouza123]

My previous post belongs in the other ECM thread, ignore it, I'll repost.