 mersenneforum.org > Data Is the "Combined" factoring probability actually wrong on mersenne.ca?
 Register FAQ Search Today's Posts Mark Forums Read  2021-06-13, 12:58 #1 Zhangrc   "University student" May 2021 Beijing, China 3·67 Posts Is the "Combined" factoring probability actually wrong on mersenne.ca? The "Combined" probability just add the trial factoring probability and the P-1 factoring probability, but that makes no sense. Take 108071849 for example: It has been trial factored to 2^77, with 64.9351% chance of finding a factor. Also, the chance of finding a factor in P-1 with b1=755000, b2=21551000 assuming no factor below 2^77 is 3.5775% (a conditional probability). Let A denote the event of "finding a factor below 2^77" B denote the event of "finding a factor in P-1 with b1=755000, b2=21551000" then P(A) = 64.9351%, P(B|(!A)) = P(!A && B) / P(!A) = 3.5775% So the total probability of finding a factor should be P(A || B) = P(A) +P(!A && B) = P(A) + P(B|(!A)) * P(!A) = P(A) + P(B|(!A)) * (1-P(!A)) = 0.0649351 + 0.035775 * (1-0.649351) = 66.1895% Which makes sense. This formula can also avoid having over 113% probability (???) on exponents such as 1277. (PS: I'm only a freshman student studying probability. If my formula is wrong, please point out :) Last fiddled with by Zhangrc on 2021-06-13 at 12:59   2021-06-14, 00:52   #2
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

13×277 Posts Quote:
 Originally Posted by Zhangrc The "Combined" probability just add the trial factoring probability and the P-1 factoring probability, but that makes no sense.
It probably doesn't. But I'm just a programmer who runs the site, my math knowledge is poor.

If others agree that your implementation makes sense I'm happy to revise the site accordingly.
But I'll need a little more explanation in simple terms what you mean with the logical combinations of probabilities, such as P(!A && B) or P(B|(!A))   2021-06-14, 03:25   #3
Zhangrc

"University student"
May 2021
Beijing, China

3×67 Posts Quote:
 Originally Posted by James Heinrich It probably doesn't. But I'm just a programmer who runs the site, my math knowledge is poor. If others agree that your implementation makes sense I'm happy to revise the site accordingly. But I'll need a little more explanation in simple terms what you mean with the logical combinations of probabilities, such as P(!A && B) or P(B|(!A))
maybe I should use TEX.
Attached Thumbnails

Last fiddled with by Zhangrc on 2021-06-14 at 03:52   2021-06-14, 03:53   #4
Zhangrc

"University student"
May 2021
Beijing, China

3·67 Posts Quote:
 Originally Posted by Zhangrc The "Combined" probability just add the trial factoring probability and the P-1 factoring probability, but that makes no sense. Take 108071849 for example: It has been trial factored to 2^77, with 64.9351% chance of finding a factor. Also, the chance of finding a factor in P-1 with b1=755000, b2=21551000 assuming no factor below 2^77 is 3.5775% (a conditional probability). Let A denote the event of "finding a factor below 2^77" B denote the event of "finding a factor in P-1 with b1=755000, b2=21551000" then P(A) = 64.9351%, P(B|(!A)) = P(!A && B) / P(!A) = 3.5775% So the total probability of finding a factor should be P(A || B) = P(A) +P(!A && B) = P(A) + P(B|(!A)) * P(!A) = P(A) + P(B|(!A)) * (1-P(!A)) = 0.0649351 + 0.035775 * (1-0.649351) = 66.1895% Which makes sense. This formula can also avoid having over 113% probability (???) on exponents such as 1277. (PS: I'm only a freshman student studying probability. If my formula is wrong, please point out :)
Sorry for a typo. The formula should be 0.649351 + 0.035775 * (1-0.649351) = 66.1895% (There was a redundant 0)   2021-06-14, 04:01   #5
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

70218 Posts Quote:
 Originally Posted by Zhangrc maybe I should use TEX.
Unfortunately that means about the same to me as this.
Attached Thumbnails   2021-06-14, 04:03   #6
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

70218 Posts Quote:
 Originally Posted by Zhangrc Sorry for a typo. The formula should be 0.649351 + 0.035775 * (1-0.649351) = 66.1895% (There was a redundant 0)
Would that always equate to

CombinedProb = TFprob + (PM1prob * (1 - TFprob))

? If so, I can work with that.   2021-06-14, 04:07 #7 Zhangrc   "University student" May 2021 Beijing, China 110010012 Posts It seems so. But you'd better wait for another one who really knows the stuff and states that the formula is correct.   2021-06-14, 06:03   #8
preda

"Mihai Preda"
Apr 2015

101010111112 Posts Quote:
 Originally Posted by James Heinrich Would that always equate to CombinedProb = TFprob + (PM1prob * (1 - TFprob)) ? If so, I can work with that.
Let's consider a story: on a dangerous trip, somebody must first cross a lake, and afterwards the forest. In the lake there's an aligator that would eat him with 90% chances. In the unlikely event that he successfully crosses the lake, he must now face a tiger in the forest, which would eat him with 60% chances. What are the chances that the person perishes in this adventure?

A) the chances of being eaten by the tiger is: "60% of 10%" == 0.6 * 0.1 == 6% (because, if the aligator gets him first, the tiger is out of luck). Overall being eaten is: 90% + 6%, 96%.

B) considering the complement: surviving the whole trip means: not being eaten by the crocodile (10%), AND not being eaten by the tiger (40%). Surviving = 10% * 40% == 4%. The complement of surviving thus is 1 - 4% == 96%, same as above.

Last fiddled with by preda on 2021-06-14 at 06:10 Reason: spelling   2021-06-14, 12:52   #9
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

E1116 Posts Quote:
 Originally Posted by preda Let's consider a story
So now I have hieroglyphs, crocodiles, and tigers. I think what you're saying is that my simplified pseudocode above is correct, but please either confirm that it is, or provide a correction if it isn't.   2021-06-14, 14:44   #10
chalsall
If I May

"Chris Halsall"
Sep 2002

23·19·67 Posts Quote:
 Originally Posted by James Heinrich So now I have hieroglyphs, crocodiles, and tigers.     2021-06-14, 15:42   #11
chris2be8

Sep 2009

2×11×101 Posts Quote:
 Originally Posted by James Heinrich I think what you're saying is that my simplified pseudocode above is correct, but please either confirm that it is, or provide a correction if it isn't.
If the probability of finding a factor by P-1 is *independent* of the probability of finding a factor by TF then your pseudocode will be correct. But if P-1 could find factors that TF would also have found then that needs to be allowed for and I don't know how to do that.

In the normal case where both TF and P-1 have only a few% chance of finding a factor adding the probabilities would be nearly right. Which is probably why it's not been noticed until now.

Chris   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Riesel Prime Search 3 2017-08-14 18:14 ixfd64 Factoring 4 2012-10-16 04:07 Mini-Geek Aliquot Sequences 15 2009-06-18 19:09 James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09 antiroach Lone Mersenne Hunters 6 2003-07-16 23:35

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

Fri Jan 21 08:49:32 UTC 2022 up 182 days, 3:18, 0 users, load averages: 1.82, 2.04, 1.85