mersenneforum.org > Math ECM on Mersenne numbers with prime exponents
 Register FAQ Search Today's Posts Mark Forums Read

 2004-04-20, 00:08 #1 biwema     Mar 2004 1011111012 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 = (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?
2004-04-20, 08:28   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2C3516 Posts

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

 2004-04-20, 18:59 #3 biwema     Mar 2004 5758 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 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.
2004-04-20, 19:55   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

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.

 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.
2021-11-01, 19:28   #7
bur

Aug 2020
79*6581e-4;3*2539e-3

1F716 Posts

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

Quote:
 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?

 2021-11-07, 09:41 #8 Happy5214     "Alexander" Nov 2008 The Alamo City 2·401 Posts 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.
2021-11-17, 21:51   #9
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

983 Posts

Quote:
 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.

2021-11-17, 23:18   #10
nordi

Dec 2016

23·3·5 Posts

Quote:
 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.

2021-11-28, 04:05   #11
Happy5214

"Alexander"
Nov 2008
The Alamo City

2×401 Posts

Quote:
 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.

Last fiddled with by Happy5214 on 2021-11-28 at 04:06 Reason: Trimming quote

 Similar Threads Thread Thread Starter Forum Replies Last Post sd235 Information & Answers 12 2018-12-06 17:56 ProximaCentauri Miscellaneous Math 22 2014-12-05 13:07 science_man_88 Miscellaneous Math 3 2010-10-13 14:32 davieddy Lounge 23 2008-06-14 17:50 T.Rex Math 12 2005-09-12 07:56

All times are UTC. The time now is 10:10.

Thu May 26 10:10:15 UTC 2022 up 42 days, 8:11, 0 users, load averages: 1.48, 1.56, 1.34