20170928, 19:37  #1 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
12155_{8} Posts 
Odds of ECM finding a factor... What a pity RDS isn't here to respond.
I'm almost afraid to ask.
I have a vague idea what the answer might be but I was only decent at Statistics and that was 40 years ago. In my GIMPS tenure (prior to this year) I have done about 6,100 small ECM assignments; virtually all in the ranges where B1=50,000 and 3 curves per assignment. Over those 6,100 assignments (18,300) curves I found 66 factors. A little better than 1% (1 per 92 assignments) or 1 per 277 curves. From here on let's round for ease of math to 6,000. If I had instead done 3,000 assignments with 6 curves each should I not have still found 66 factors? I suspect not quite. 300 assignments with 60 curves each ... still 66 factors? I suspect moreso not quite. 66 assignments with 273 curves each ... still 66 factors? Certainly not. Where have I strayed? Thanks 
20170928, 19:41  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
19CC_{16} Posts 
After running one curve the odds of the next curve finding a factor are diminished. Each curve reduces the odds for future curves.

20170928, 19:56  #3  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
3^{2}×7×83 Posts 
Quote:
But from curve 1 to curve 100 for example it seems to me that the odds would not diminish a lot? In any case then, does this suggest that if, for example, I plan to do onemeeeeellllion curves in the B1=50,000 range that I would find MANY more factors doing a lower number of curves on a larger number of different exponents. I'm trying to balance better odds of finding a factor against doing a ton of very quick assignments. So for example if the odds of doing 100 curves is close to 10X the odds of doing 10 curves (on exponents with very few prior curves) I would rather do so. But if the odds of doing 100 curves is closer to only 5X then I probably would lower the number of curves and do more different exponents. In a nutshell, any idea where the "sweet spot" might be? Last fiddled with by petrw1 on 20170928 at 20:08 Reason: Last paragraph 

20170928, 19:57  #4 
Einyen
Dec 2003
Denmark
2^{2}×7×11^{2} Posts 
I have only 46 factors in 15780 ECM "attempts", but I'm not sure how many curves that is.
I have always just run WorkPreference=5 and let the server decide. Right now it is only giving me 1 curve at the time, I seem to remember it was 3 curves sometimes, but maybe that is because I have MaxExponents=1 ? I will try to raise it to 3. Edit: Nope with MaxExponents=3 I just get 3 exponents with 1 curve each. Last fiddled with by ATH on 20170928 at 20:06 
20170928, 20:02  #5 
Aug 2006
1763_{16} Posts 
If there is a factor you can find at that level, each curve is just as likely as any other to find it. But there might not be a factor you can find, and the more you fail to find a factor the more likely you're in the second case rather than the first.

20170928, 20:16  #6  
Aug 2006
1763_{16} Posts 
Quote:
But of course there may not be a factor of that size. The chance that a 'random' number* has a 25digit factor is 0.04, so if you had such a number you'd start out being 96% certain it didn't have a 25digit factor and after running 100 curves you'd be 97.1% and after the full 280 you'd be 98.4% sure. * Yes, there is no uniform probability distribution over the integers, but you can use limits or the supernatural numbers to get the expected result in this case. Quote:
If you're removing factors as you find them, there are fewer factors to find as you go and so it gets harder and harder to find them, until at last you've found them all and it's not possible to find any more no matter how many curves you run. 

20170928, 20:16  #7  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
3^{2}·7·83 Posts 
Quote:
MaxExponents is not relevant. I think George programmed it such that assignments get 3 curves in general but it drops to 1 curve if the GhzDays for 3 curves exceeds some magical number (maybe around 1) ... or at some exponent value. I am getting 3 curves for 67M and 1 curve for 1217M. 

20170928, 20:34  #8  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
5229_{10} Posts 
Quote:
I'm confused on the 0.04 (5%), though. The B1=50,000 range suggests it is looking for factors from 25 to 29 digits. That is about 80  96 bits. If I use the formula from here: https://www.mersenne.org/various/math.php Quote:


20170928, 20:41  #9  
"Curtis"
Feb 2005
Riverside, CA
1573_{16} Posts 
Quote:


20170928, 20:42  #10 
Aug 2002
Buenos Aires, Argentina
2·17·43 Posts 
ECM with B1 = 50000 is intended for finding prime factors up to 25 digits. Sometimes it finds larger prime factors, but if you want to find prime factors up to 30 digit, you will need to use the next level, i.e. B1 = 250000 with the appropriate number of curves.

20170928, 21:30  #11  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
3^{2}·7·83 Posts 
Quote:
From the TF done on these exponents eligible for ECM (under 20M); most of them are up to 6567 bits or approximately 19 or 20 digits; and many that of the smaller exponents with less TF already have a decent amount of ECM done. I am focusing on the exponents with very little ECM done. From 20 to 25 digits is close to the odds of TF from 67 to 83 bits or almost 23%...even better. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Odds of Finding a Factor  Gordon  Factoring  18  20150920 20:33 
how much ECM without finding an existing factor  dbaugh  PrimeNet  4  20130111 16:31 
p1 testing ram vs finding a factor  crash893  Software  11  20060703 21:48 
Probability of finding a factor  JuanTutors  Software  20  20040926 09:47 
possibility of finding a factor  there_is_no_spoon  Math  10  20040311 20:05 