Odds of ECM finding a factor... What a pity RDS isn't here to respond.

[petrw1]

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

[retina]

After running one curve the odds of the next curve finding a factor are diminished. Each curve reduces the odds for future curves.

[petrw1]

Originally Posted by retina

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?

[ATH]

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.

[CRGreathouse]

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]

Originally Posted by petrw1

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.

Originally Posted by petrw1

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.

[petrw1]

Originally Posted by ATH

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]

Originally Posted by CRGreathouse

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

the chance of finding a factor between 2X and 2X+1 is about 1/x.

then from 80 - 96 bits I get over 19%.

[VBCurtis]

Originally Posted by petrw1

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.

[alpertron]

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.

[petrw1]

Originally Posted by alpertron

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.