mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-04-20, 00:08   #1
biwema
 
biwema's Avatar
 
Mar 2004

1011111012 Posts
Default 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?
biwema is offline   Reply With Quote
Old 2004-04-20, 08:28   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2C3516 Posts
Default

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
xilman is online now   Reply With Quote
Old 2004-04-20, 18:59   #3
biwema
 
biwema's Avatar
 
Mar 2004

5758 Posts
Default

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.
biwema is offline   Reply With Quote
Old 2004-04-20, 19:55   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Old 2004-04-21, 04:03   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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 is offline   Reply With Quote
Old 2004-04-21, 04:44   #6
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

My previous post belongs in the other ECM thread, ignore it, I'll repost.
dsouza123 is offline   Reply With Quote
Old 2021-11-01, 19:28   #7
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

1F716 Posts
Default

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?
bur is offline   Reply With Quote
Old 2021-11-07, 09:41   #8
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

2·401 Posts
Default

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.
Happy5214 is offline   Reply With Quote
Old 2021-11-17, 21:51   #9
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

983 Posts
Default

Quote:
Originally Posted by bur View Post
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.
kruoli is offline   Reply With Quote
Old 2021-11-17, 23:18   #10
nordi
 
Dec 2016

23·3·5 Posts
Default

Quote:
Originally Posted by kruoli View Post
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.
nordi is offline   Reply With Quote
Old 2021-11-28, 04:05   #11
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

2×401 Posts
Default

Quote:
Originally Posted by nordi View Post
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
Happy5214 is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”