mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-03-12, 07:59   #1
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2·4,481 Posts
Default 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
LaurV is online now   Reply With Quote
Old 2012-03-12, 08:42   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
Batalov is offline   Reply With Quote
Old 2012-03-12, 09:05   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Default

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. :-)
Batalov is offline   Reply With Quote
Old 2012-03-12, 09:13   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×4,481 Posts
Default

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!"
LaurV is online now   Reply With Quote
Old 2012-03-12, 09:18   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×4,481 Posts
Default

Quote:
Originally Posted by Batalov View Post
Here's a silly example.
...<snip>...
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...
LaurV is online now   Reply With Quote
Old 2012-03-12, 17:49   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2012-03-12, 18:19   #7
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23×3×7×43 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
Prime95 is offline   Reply With Quote
Old 2012-03-12, 18:45   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2·4,481 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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.
LaurV is online now   Reply With Quote
Old 2012-03-12, 21:15   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

918210 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2012-03-12, 23:14   #10
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 View Post
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^{<br />
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
Mini-Geek is offline   Reply With Quote
Old 2012-03-13, 01:43   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

230216 Posts
Default

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...
LaurV is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Need Some Papers on mersenne numbers kurtulmehtap Math 5 2012-10-10 03:01
medication and Mersenne numbers ? science_man_88 Miscellaneous Math 0 2010-08-06 21:18
6 digit numbers and the mersenne numbers henryzz Math 2 2008-04-29 02:05
Question about Mersenne Numbers rong123 Marin's Mersenne-aries 7 2007-11-09 00:34
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 08:25.

Thu Dec 3 08:25:41 UTC 2020 up 4:36, 0 users, load averages: 0.93, 1.00, 0.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.