mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2015-05-25, 10:14   #1
westicles
 
May 2015

710 Posts
Default ECM odds

I apologize for the remedial newbie question.

For M<1e6 and the GIMPS choices for B1/B2/number of curves tested, I would like to estimate the odds that the last curve of one B1/B2 range finds a factor, versus the first curve of the next range. Can someone provide a reference/equation to help?
westicles is offline   Reply With Quote
Old 2015-05-25, 15:48   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

The question is more complicated that it sounds. If a factor of a particular size exists, the probability of finding that factor is the same for every curve of the set. But that includes re-finding factors already found by earlier curves in the set. And you seldom know that a factor of a particular size exists, so working through a set curves without finding any such factor makes it more likely that a factor of that size does not exist. These are not particularly complicated probability ideas, but there are several things to keep track of. We could help you work through them if you want.

But the answer you probably want can be figured out in a simpler manner. Recommended change points happen because the probability of finding a factor per unit of computing power has just become higher for the bigger curve. So right at the change over the probabilities are the same. (In fact, they are nearly the same for a broad range around the change point, but that's not necessary for this argument). So if the new curve takes "k" times more computing power, it is "k" times more likely to find a factor. If it were not so, the recommended change point would be early or later - at the point where it IS true.

So if you only want the relative odds - that's how to do it. If you want to know the actual values of these probabilities, we need to dig deeper into the issues of the first paragraph.
wblipp is offline   Reply With Quote
Old 2015-05-25, 17:12   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by wblipp View Post
The question is more complicated that it sounds. If a factor of a particular size exists, the probability of finding that factor is the same for every curve of the set. But that includes re-finding factors already found by earlier curves in the set. And you seldom know that a factor of a particular size exists, so working through a set curves without finding any such factor makes it more likely that a factor of that size does not exist. These are not particularly complicated probability ideas, but there are several things to keep track of. We could help you work through them if you want.

But the answer you probably want can be figured out in a simpler manner. Recommended change points happen because the probability of finding a factor per unit of computing power has just become higher for the bigger curve. So right at the change over the probabilities are the same. (In fact, they are nearly the same for a broad range around the change point, but that's not necessary for this argument). So if the new curve takes "k" times more computing power, it is "k" times more likely to find a factor. If it were not so, the recommended change point would be early or later - at the point where it IS true.

So if you only want the relative odds - that's how to do it. If you want to know the actual values of these probabilities, we need to dig deeper into the issues of the first paragraph.
The reply was almost totally devoid of information. It is hand-waving nonsense.

The OP's question may be answered by reading my joint paper with Sam Wagstaff Jr.:
A Practical Analysis of ECM, Math. Comp.
R.D. Silverman is offline   Reply With Quote
Old 2015-05-25, 20:44   #4
westicles
 
May 2015

7 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
The OP's question may be answered by reading my joint paper with Sam Wagstaff Jr.:
A Practical Analysis of ECM, Math. Comp.
Great paper, thank you.

It would take some time to recreate your Bayesian analysis for these specific bounds, but it seems clear that the first curve in the next range will have a better chance of finding a factor well before you finish the previous range, even if you account for the longer run time. It would be interesting to come up with an optimal scheme to fill out the ranges non-sequentially.
westicles is offline   Reply With Quote
Old 2015-05-25, 22:04   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
The reply was almost totally devoid of information. It is hand-waving nonsense.

The OP's question may be answered by reading my joint paper with Sam Wagstaff Jr.:
A Practical Analysis of ECM, Math. Comp.
If he only wants the relative odds, the only thing he needs from your paper is the discovery that the response curve is flat - I gave him that and told him how to use it.

I also laid the groundwork for why he would need your paper. I suspected he would not want that level of detail, but it appears I was wrong about that. I'm a little to slow to actually recommend the paper because of the error in the rho function at the beginning. It's a great paper for the sufficiently savvy to get the concept, and you have assured me that the results used the correct rho function. But the error can be a stumbling block for anyone hoping to get numeric results from the paper.
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What are the odds? petrw1 PrimeNet 0 2016-10-06 22:40
Odds Fred Software 4 2016-03-08 03:05
Seems to defy the odds.... petrw1 Factoring 6 2013-03-19 00:21
odds in genetics. science_man_88 Science & Technology 10 2010-11-09 22:01
ARE THE ODDS CORRECT..Please help lpmurray Lounge 4 2005-02-09 10:38

All times are UTC. The time now is 18:05.

Mon Nov 30 18:05:11 UTC 2020 up 81 days, 15:16, 3 users, load averages: 3.05, 2.76, 2.34

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.