mersenneforum.org Probability of finding a factor
 Register FAQ Search Today's Posts Mark Forums Read

 2004-06-21, 22:49 #1 JuanTutors     Mar 2004 2×13×19 Posts Probability of finding a factor For some of the math people who maybe know something about the software, what is the approximate probability of finding a factor of M34000009 if you trial factor from 2^62 to 2^68 and you give @200Mb of ram to the P-1 factoring?
 2004-06-22, 23:36 #2 JuanTutors     Mar 2004 1111011102 Posts Should this be in the Programming or Math section instead?
 2004-06-23, 00:19 #3 marc     Jun 2004 UK 139 Posts http://mersenne.org/math.htm says that the probability of finding a factor between 2^x and 2^(x+1) is 1/x. So if we're trial-factoring between 62 and 68 then the chance we don't find a factor is 61/62 * 62/63 * ... * 67/68 which simplifies to 61/68. The chance of finding a factor between 62 and 68 is 7/68. Someone will correct me if I made any mistakes.
 2004-06-23, 01:11 #4 Axel Fox     May 2003 9610 Posts Actually your chance is 1/62 + 1/63 + 1/64 + 1/65 + 1/66 + 1/67 which is (using a calculator) roughly 9.31 %
 2004-06-23, 01:54 #5 marc     Jun 2004 UK 139 Posts That's the chance a factor exists in just 1 of those ranges. It's possible a factor exists between 62 and 63 and another factor exists between 65 and 66 which means you're very slightly underestimating the chances.
2004-06-23, 02:19   #6
nfortino

Nov 2003

3·5·11 Posts

Quote:
 Originally Posted by marc http://mersenne.org/math.htm says that the probability of finding a factor between 2^x and 2^(x+1) is 1/x. So if we're trial-factoring between 62 and 68 then the chance we don't find a factor is 61/62 * 62/63 * ... * 67/68 which simplifies to 61/68. The chance of finding a factor between 62 and 68 is 7/68. Someone will correct me if I made any mistakes.
Your logic is a bit flawed, as you have the wrong bounds for your multiplication. You want to multiply the probability of not finding a factor between 62 and 63 bits, by the probability of not finding a factor between 63 and 64 bits...by the probability of not finding a factor between 67 bits and 68 bits. This is 61/62*62/63*...*66/67. Since the probability of finding a factor between 67 bits and 68 bits is 1/67, the sequence of multiplication must end at 66/67, not 67/68. This gives an answer of 6/67 or a little less than 9%.

As for Angel Fox, you have calculated the expected number of factors, not the probability of finding a factor. If you don't believe your answer is wrong, try doing the same calculation if you are factoring to a very large number of bits. You will find you get n answer greater than one, which is clearly not a probability.

 2004-06-23, 02:33 #7 Axel Fox     May 2003 25·3 Posts I know that nfortino, but given a number of probabilities Pi for i=1..n, the probability that one of the cases 1..n is true is P1+P2+P3 ... +Pn and normally, the sum of all Pi for every possible i is 1. However, the given probability of 1/X is only an aproximation, not a real probability and that is why you (eventually) get a number greater than 1. The series 1/X + 1/X+1 + 1/X+2 ... is even a part of the harmonic series and if I'm not mistaking that series diverges (goes to infinity if you go to X=infinity). So, if you factor to infinity bits, that would mean (by your definition of 1/X being the number of factors) that a certain number would have an infinite number of factors, which is also not true. Both of these contradiction result from the fact that 1/X is only an approximation and not a real probability function.
 2004-06-23, 04:14 #8 Kevin     Aug 2002 Ann Arbor, MI 433 Posts Axel Fox: The probability of finding a factor doesn't add up to one......if it did, that would kinda make it hard to find primes Secondly, you can't just add the probabilities. Can I roll a 6-sided die 7 times and have a 116.666666666% chance of rolling a 6? Also, why exactly would we factor to infinite bits? Methinks any factoring past p bits would be a might bit redundant... My thinking is that P(finding factor)=1-P(not finding factor)=1-[(61/62)*(62/63)*(63/64)...*(67/68)]=7/68
2004-06-23, 05:43   #9
wblipp

"William"
May 2003
New Haven

22·32·5·13 Posts

Quote:
 Originally Posted by Axel Fox but given a number of probabilities Pi for i=1..n, the probability that one of the cases 1..n is true is P1+P2+P3 ... +Pn
This only works when the events are mutually exclusive. For example, if you throw two dice, the probablity of getting at least one "1" is 11/36, and the probability of at least one "2" is 11/36, but the probability of rolling at least one value less than 3 is 20/36, not 22/36.

 2004-06-23, 06:19 #10 markr     "Mark" Feb 2003 Sydney 13×43 Posts Let's see if I can help clarify - or only confuse! Kevin & marc: you have the right approach, but seven parts in your calculation where there should be six - the number of intervals between 62 & 68. The last part is the chance of not finding a factor between 67 & 68: 66/67. So the probability is 6/67 = 8.9552% Axel Fox: the sum of all Pi is only 1 if the events don't overlap. When the program finds a factor, it stops & doesn't look in higher ranges. So P(factor found between 63 & 64) is actually P(factor exists between 63 & 64).P(no factor exists between 62 & 63), and so on. Just to check, I worked it out: P(factor found between 62 & 68) = P(factor between 62 & 63) + P(no factor between 62 & 63).P(factor between 63 & 64) + P(no factor between 62 & 64).P(factor between 64 & 65) + ... + P(no factor between 62 & 67).P(factor between 67 & 65) = 1/62 + (61/62).(1/63) + (61/62).(62/63).(1/64) + ... + (61/62).(62/63).(63/64).(64/65).(65/66).(1/67) which is numerically the same as 6/67. [I used a spreadsheet... ] That last part should have helped confuse!
2004-06-23, 08:00   #11
MrHappy

Dec 2003
Paisley Park & Neverland

5·37 Posts

Quote:
 Originally Posted by marc http://mersenne.org/math.htm says that the probability of finding a factor between 2^x and 2^(x+1) is 1/x.
We believe that - we don't know it.

 Similar Threads Thread Thread Starter Forum Replies Last Post nuggetprime Math 2 2011-03-19 22:14 optim Math 2 2003-12-06 19:03 eepiccolo Math 4 2003-06-07 05:56 Deamiter Math 4 2002-12-25 06:06 Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 12:52.

Thu Oct 22 12:52:07 UTC 2020 up 42 days, 10:03, 0 users, load averages: 1.77, 2.06, 2.05