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.

[bur]

I know this thread is old, but I couldn't find any other explanation more detailed than

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.

A 41 digits for M14731 was found via ECM with B1=3,000,000 and sigma=1633953865112230. I calculated the group order and got 38152341450307720350443047374123628167912 = 2^3 * 3 * 17 * 29 * 6424761361 * 501887101220020068394859531 which is too large for that B1 and B2.

I guess that's as expected, but I couldn't figure out how to use that to calculate the correct group order. I used this script. I assume it has to be rewritten to be used for Mersenne factors?

[Happy5214]

I usually have success adding my GIMPS ECM factors to FactorDB using the standard group order formula. I used to dump my aliquot ECM factors into FactorDB regularly, and I ran into similar errors as you on rare occasions, so I'm not sure it's Mersenne-related. I never understood what exactly happened in those instances.

[kruoli]

Originally Posted by bur

A 41 digits for M14731 was found via ECM with B1=3,000,000 and sigma=1633953865112230.

Trying this as in ecm -v -sigma 0:1633953865112230 3000000 300000000 (and entering 2^14731-1) did not result in a factor for me.

[nordi]

Originally Posted by kruoli

Trying this as in ecm -v -sigma 0:1633953865112230 3000000 300000000 (and entering 2^14731-1) did not result in a factor for me.

I originally found this factor using mprime, not gmp-ecm. I'm not sure if the Sigma values are "compatible", i.e. if the same Sigma yields the same result in both programs. I have no idea about Bur's question about group order, btw.

[Happy5214]

Originally Posted by nordi

I originally found this factor using mprime, not gmp-ecm. I'm not sure if the Sigma values are "compatible", i.e. if the same Sigma yields the same result in both programs.

I checked various versions of the mprime source (29.8, 30.3, and the latest release of 30.7), and they all purport to use the same Suyama parameterization used by GMP-ECM for -param 0 (the default), so they should be compatible. I'll admit that I just looked at the code comments and not the actual code, since I haven't worked with gwnum before and thus am not fluent in reading it.