mersenneforum.org > Math ECM question for mersenne numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2012-03-12, 07:59 #1 LaurV Romulan Interpreter     Jun 2011 Thailand 3·47·67 Posts ECM question for mersenne numbers Say I want to be the proud owner of a found-by-ecm 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 i7-2600k 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 4-cores 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 3-curves, 3-curves, 3-curves, 3-curves, 3-curves, 3-curves, 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", p-1 done/notdone, etc]. Thanks in advance. Last fiddled with by LaurV on 2012-03-12 at 08:06
2012-03-12, 08:42   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,431 Posts

Quote:
 Originally Posted by LaurV The question is, do I have any chance to find an ECM factor
Of course!
Quote:
 or should I quit dreaming and put my 4-cores 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?
Anything is possible but a year (or years) would be a better ballpark.

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^n-1 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.

 2012-03-12, 09:05 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100110101112 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 ...but is this at all interesting? I think that it is as valuable as the time spent, i.e. totally negligible. :-)
 2012-03-12, 09:13 #4 LaurV Romulan Interpreter     Jun 2011 Thailand 3×47×67 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 40-digits 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!"
2012-03-12, 09:18   #5
LaurV
Romulan Interpreter

Jun 2011
Thailand

3·47·67 Posts

Quote:
 Originally Posted by Batalov Here's a silly example. ...... i.e. totally negligible. :-)
(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...

 2012-03-12, 17:49 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,431 Posts Sorry to hear that. I'll rephrase. 362413410829912982364271 is a new factor of 2^7745-1, which is a Mersenne number. Phi7745(2) is one of its factors. This was a trivial illustration how to get what you wanted - and fast.
2012-03-12, 18:19   #7
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

22·1,873 Posts

Quote:
 Originally Posted by Batalov Anything is possible but a year (or years) would be a better ballpark.
I think days or weeks would be a better estimate. New ECM factors on these medium-sized Mersenne numbers aren't all that rare.

Last fiddled with by Prime95 on 2012-03-12 at 18:20

2012-03-12, 18:45   #8
LaurV
Romulan Interpreter

Jun 2011
Thailand

100100111001112 Posts

Quote:
 Originally Posted by Prime95 I think days or weeks would be a better estimate. New ECM factors on these medium-sized Mersenne numbers aren't all that rare.
My estimation based on numerical analysis of the attempts/successes on this page and on my computing power, gave me an optimistic 9 days, or a non-optimistic 13 days. But I wanted to grasp the theory behind of those numbers. I mean it is very clear for me (from the example given on the math page about LL tests) how the "chance of some exponent to be prime" is computed, and why. What I wanted was some equivalent explication for ecm.

 2012-03-12, 21:15 #9 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 223278 Posts I've now used this page. There are three F-ECM 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.
2012-03-12, 23:14   #10
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts

Quote:
 Originally Posted by LaurV 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", p-1 done/notdone, etc]. Thanks in advance.
Quote:
 Originally Posted by LaurV My estimation based on numerical analysis of the attempts/successes on this page and on my computing power, gave me an optimistic 9 days, or a non-optimistic 13 days. But I wanted to grasp the theory behind of those numbers. I mean it is very clear for me (from the example given on the math page about LL tests) how the "chance of some exponent to be prime" is computed, and why. What I wanted was some equivalent explication for ecm.
GIMPS' math page says, regarding P-1:
Quote:
 Dickman's function (see Knuth's Art of Computer Programming Vol. 2) is used to determine the probability of finding a factor, that is k is B1-smooth or B1-smooth with just one factor between B1 and B2.
The same thing, roughly, applies to ECM, since the group orders of the factors you find are about the size of the factors found. So the answer to your question regarding the probability of finding a factor will be found in Dickman's function. Since you'll be doing stage 2 as well, you'll need the 2-dimensional analog described in the Extension section of that document, which is described in this paper. My math-fu is only strong enough to vaguely grasp this estimate:
Where $\Psi(x,B1,B2)$ is the count of numbers below x that meet bounds B1 and B2:
$\Psi(x,x^{1/a},x^{1/b})\sim x\sigma(b,a)$
And $\sigma$ is approximated by:
$\sigma(u, v) \approx e^{
4.55219-0.933064u \log u-0.280283v \log v}$

It might be more practical to look at the code of GMP-ECM or Prime95 that handles ECM probabilities and see how they do it. In GMP-ECM, see ecm.c's print_expcurves method and rho.c's ecmprob method. Note that these don't consider previous TF and P-1. 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 Mini-Geek on 2012-03-12 at 23:19

 2012-03-13, 01:43 #11 LaurV Romulan Interpreter     Jun 2011 Thailand 223478 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post kurtulmehtap Math 5 2012-10-10 03:01 science_man_88 Miscellaneous Math 0 2010-08-06 21:18 henryzz Math 2 2008-04-29 02:05 rong123 Marin's Mersenne-aries 7 2007-11-09 00:34 T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 02:04.

Fri May 14 02:04:11 UTC 2021 up 35 days, 20:45, 0 users, load averages: 2.70, 2.90, 2.89