mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-09-28, 19:37   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

11C716 Posts
Default 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
petrw1 is online now   Reply With Quote
Old 2017-09-28, 19:41   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

35×52 Posts
Default

After running one curve the odds of the next curve finding a factor are diminished. Each curve reduces the odds for future curves.
retina is online now   Reply With Quote
Old 2017-09-28, 19:56   #3
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3·37·41 Posts
Default

Quote:
Originally Posted by retina View Post
After running one curve the odds of the next curve finding a factor are diminished. Each curve reduces the odds for future curves.
So if the chart wants 280 curves at the B1=50,000 range then the last few curves would have almost no chance.

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 one-meeeeellllion 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 2017-09-28 at 20:08 Reason: Last paragraph
petrw1 is online now   Reply With Quote
Old 2017-09-28, 19:57   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1011110101112 Posts
Default

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 2017-09-28 at 20:06
ATH is offline   Reply With Quote
Old 2017-09-28, 20:02   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135248 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2017-09-28, 20:16   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×1,493 Posts
Default

Quote:
Originally Posted by petrw1 View Post
So if the chart wants 280 curves at the B1=50,000 range then the last few curves would have almost no chance.

But from curve 1 to curve 100 for example it seems to me that the odds would not diminish a lot?
The chart is usually designed so that if you do the recommended number of curves, the chance of missing a factor of the given size is 1/e. So if the chance of finding a factor on a single curve is p, the chance of missing it is 1 - p and the chance of missing it with 280 curves is (1 - p)^280 = 1/e and so p = 0.003565....

But of course there may not be a factor of that size. The chance that a 'random' number* has a 25-digit factor is 0.04, so if you had such a number you'd start out being 96% certain it didn't have a 25-digit 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:
Originally Posted by petrw1 View Post
In any case then, does this suggest that if, for example, I plan to do one-meeeeellllion 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.
If you test the same number each time, each test will work the same way.

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.
CRGreathouse is offline   Reply With Quote
Old 2017-09-28, 20:16   #7
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3×37×41 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
My recent ECM work (hence why my first post excluded this year) if for exponents under 20,000 which uses much higher bounds. My ratio there is 2 factors in 161,000 curves.

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 6-7M and 1 curve for 12-17M.
petrw1 is online now   Reply With Quote
Old 2017-09-28, 20:34   #8
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

107078 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
The chance that a 'random' number* has a 25-digit factor is 0.04, so if you had such a number you'd start out being 96% certain it didn't have a 25-digit factor and after running 100 curves you'd be 97.1% and after the full 280 you'd be 98.4% sure.

If you're removing factors as you find them, there are fewer factors to find as you go
Thanks; what you explained makes sense.

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:
the chance of finding a factor between 2X and 2X+1 is about 1/x.
then from 80 - 96 bits I get over 19%.
petrw1 is online now   Reply With Quote
Old 2017-09-28, 20:41   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·5·467 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Thanks; what you explained makes sense.

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

then from 80 - 96 bits I get over 19%.
The 4% you quoted was given to you as specifically a 25-digit factor. You replied with the chance of a 25 to 29 digit factor. Both are correct [estimates]. Absent any knowledge of prior factoring efforts, the chances a number has a factor of n digits is approximated by 1/n. 1/25 is 4%; 1/25 + 1/26 + 1/27 + 1/28 + 1/29 is roughly the 19% you cite.
VBCurtis is offline   Reply With Quote
Old 2017-09-28, 20:42   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·11·61 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2017-09-28, 21:30   #11
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

10001110001112 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
oops bad assumption in my case..what the 25 meant.

From the TF done on these exponents eligible for ECM (under 20M); most of them are up to 65-67 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.
petrw1 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odds of Finding a Factor Gordon Factoring 18 2015-09-20 20:33
how much ECM without finding an existing factor dbaugh PrimeNet 4 2013-01-11 16:31
p-1 testing ram vs finding a factor crash893 Software 11 2006-07-03 21:48
Probability of finding a factor JuanTutors Software 20 2004-09-26 09:47
possibility of finding a factor there_is_no_spoon Math 10 2004-03-11 20:05

All times are UTC. The time now is 20:23.

Thu Feb 25 20:23:25 UTC 2021 up 84 days, 16:34, 1 user, load averages: 1.80, 1.68, 1.77

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