ECM on Mersenne numbers with prime exponents

biwema · 2004-04-20, 00:08

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 · 2004-04-20, 08:28

Quote:

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 · 2004-04-20, 18:59

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 · 2004-04-20, 19:55

Quote:

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 · 2004-04-21, 04:03

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 · 2004-04-21, 04:44

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

2004-04-20, 00:08	#1
biwema Mar 2004 381₁₀ Posts	ECM on Mersenne numbers with prime exponents 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 = (2kexp) + 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 2exp? Sigma = 2kexp. 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Why have ECM testing for known non-prime Mersenne numbers?	sd235	Information & Answers	12	2018-12-06 17:56
Another interesting pattern of Mersenne exponents: they are prime!!!!1111	ProximaCentauri	Miscellaneous Math	22	2014-12-05 13:07
Mersenne(prime exponents) factorization	science_man_88	Miscellaneous Math	3	2010-10-13 14:32
Are Mersenne numbers more likely tobe prime?	davieddy	Lounge	23	2008-06-14 17:50
A property of prime Mersenne numbers under LLT	T.Rex	Math	12	2005-09-12 07:56

2004-04-20, 18:59	#3
biwema Mar 2004 3×127 Posts	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 2exp? That we choose sigma, that the group order is p - 1 + 2exp. 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.

2004-04-21, 04:03	#5
dsouza123 Sep 2002 2·331 Posts	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 ?

2004-04-21, 04:44	#6
dsouza123 Sep 2002 2×331 Posts	My previous post belongs in the other ECM thread, ignore it, I'll repost.