20120312, 07:59  #1 
Romulan Interpreter
Jun 2011
Thailand
5^{2}×7×53 Posts 
ECM question for mersenne numbers
Say I want to be the proud owner of a foundbyecm factor of a mersenne number. I never did "intentional" ECM (as opposed to the one occasionally assigned by the server to my machines having "whatever makes sense" as default). Now, I set a full i72600k to ECM small mersenne numbers with p95. It is already working, and reported 90 curves over the weekend, (3 curves for 30 exponents in the 6.6M range).
The question is, do I have any chance to find an ECM factor or should I quit dreaming and put my 4cores to something more useful? And here we come to the math part, how big is my chance to find a factor, in the next (couple of) days? (24/7 on, lots of memory). Is it better to let P95 assign me 3curves, 3curves, 3curves, 3curves, 3curves, 3curves, etc, on 1000 exponents (as it seems to behave), or should I manually take a bucket of curves (100, 150, 200) on 4 exponents (one for each core) and let it run? [edit: I am talking about the initialization part when the exponent changes, wouldn't be more useful to keep one expo for more curves?]. I would be interested in the math part (or a link to it) [edit: about probabilities to find factors, given the range and the "how far factored", p1 done/notdone, etc]. Thanks in advance. Last fiddled with by LaurV on 20120312 at 08:06 
20120312, 08:42  #2  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×13×359 Posts 
Of course!
Quote:
The server will give you reasonable tasks. If you want to do all that math yourself (get the counts of already done curves, estimate probabilities etc etc)  all certainly doable, the data is also public. There are ways to get "a" factor faster (not a very notable factor though, but they will get you recorded e.g. here)  that is for cofactors of 2^n1 with n not prime and higher than currently "wanted" (GIMPS covers n prime traditionally). Don't get your hopes too high  this path is also not a walk in the park: even these are ECM'd a lot. For that path, the burden of finding out how much is already done is heavier. And they are not really wanted. Yet another way is to contribute to finding a factor of M929. You will be able to say: there's a small part of my work in this and thsi factor. 

20120312, 09:05  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010001110110_{2} Posts 
Here's a silly example.
I want a new factor. I take a arbitrarily large composite n=7745. I observe that only a small factor 46471 is known for Phi(7745,2). I throw a few small curves. And I get Code:
Input number is (Phi(7745,2))/46471 (1860 digits) Using B1=250000, B2=183032866, polynomial Dickson(3), sigma=2006014604 Step 1 took 28541ms Step 2 took 12445ms ********** Factor found in step 2: 362413410829912982364271 Found probable prime factor of 24 digits: 362413410829912982364271 Composite cofactor ((Phi(7745,2))/46471)/362413410829912982364271 has 1836 digits 
20120312, 09:13  #4 
Romulan Interpreter
Jun 2011
Thailand
5^{2}×7×53 Posts 
Hmmm, you may be totally right. I still don't get a feeling to why and how. And of course I am not aspiring so high as in the list you linked, say a 30 or 40digits ECM factor for a M66xxxxx would be my target , so I could come back here and brag "hey, look, I have an ECM factor too!"

20120312, 09:18  #5 
Romulan Interpreter
Jun 2011
Thailand
5^{2}·7·53 Posts 
(you posted in between, during I was editing) I am not talking about that, of course I found plenty of ECM factors crunching into aliquot sequences, but that, as you say, does not count. I am talking strictly about mersenne numbers, and strictly about p95 assignments. I don't know how to do the math by myself, otherwise I won't ask...

20120312, 17:49  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·13·359 Posts 
Sorry to hear that.
I'll rephrase. 362413410829912982364271 is a new factor of 2^77451, which is a Mersenne number. Phi_{7745}(2) is one of its factors. This was a trivial illustration how to get what you wanted  and fast. 
20120312, 18:19  #7 
P90 years forever!
Aug 2002
Yeehaw, FL
1110011000101_{2} Posts 
I think days or weeks would be a better estimate. New ECM factors on these mediumsized Mersenne numbers aren't all that rare.
Last fiddled with by Prime95 on 20120312 at 18:20 
20120312, 18:45  #8  
Romulan Interpreter
Jun 2011
Thailand
5^{2}·7·53 Posts 
Quote:


20120312, 21:15  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22166_{8} Posts 
I've now used this page. There are three FECM hits on it (over ~25 hours), but divide this by number of ECM participants and also note that this kind of hits will not really get your name recorded anywhere. Example. I appreciate that OP may have meant just the feeling of accomplishment (for one's own adrenaline) and that is fine! It is a great thing to have tried everything.
I was thinking years for notable exponents, say, under 15000. Under 1200, we (simple home users) can pretty much forget about an ECM success. 
20120312, 23:14  #10  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Quote:
Quote:
Quote:
Where is the count of numbers below x that meet bounds B1 and B2: And is approximated by: It might be more practical to look at the code of GMPECM or Prime95 that handles ECM probabilities and see how they do it. In GMPECM, see ecm.c's print_expcurves method and rho.c's ecmprob method. Note that these don't consider previous TF and P1. Presumably you could find that in Prime95. As you can probably see, the only easy answers (AFAICT) to your question is: "it's complicated", and "go look at how someone else did it". Here are some pages with more info on the math behind ECM: http://mersennewiki.org/index.php/Elliptic_curve_method http://en.wikipedia.org/wiki/Lenstra..._factorization Last fiddled with by MiniGeek on 20120312 at 23:19 

20120313, 01:43  #11 
Romulan Interpreter
Jun 2011
Thailand
5^{2}·7·53 Posts 
Thanks a lot. Let me digest the math part few days (I saved the pdfs and links), at a first look (busy at job, just arrived) I didn't understand anything...

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Need Some Papers on mersenne numbers  kurtulmehtap  Math  5  20121010 03:01 
medication and Mersenne numbers ?  science_man_88  Miscellaneous Math  0  20100806 21:18 
6 digit numbers and the mersenne numbers  henryzz  Math  2  20080429 02:05 
Question about Mersenne Numbers  rong123  Marin's Mersennearies  7  20071109 00:34 
LLT numbers, linkd with Mersenne and Fermat numbers  T.Rex  Math  4  20050507 08:25 