Probability of finding a factor

JuanTutors · 2004-06-21, 22:49

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?

JuanTutors · 2004-06-22, 23:36

Should this be in the Programming or Math section instead?

marc · 2004-06-23, 00:19

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.

Axel Fox · 2004-06-23, 01:11

Actually your chance is

1/62 + 1/63 + 1/64 + 1/65 + 1/66 + 1/67

which is (using a calculator) roughly 9.31 %

marc · 2004-06-23, 01:54

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.

nfortino · 2004-06-23, 02:19

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.

Axel Fox · 2004-06-23, 02:33

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.

Kevin · 2004-06-23, 04:14

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

wblipp · 2004-06-23, 05:43

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.

markr · 2004-06-23, 06:19

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!

MrHappy · 2004-06-23, 08:00

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.

2004-06-21, 22:49	#1
JuanTutors Mar 2004 3×167 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Probability of factor (TF)	nuggetprime	Math	2	2011-03-19 22:14
probability of finding a Mersenne prime	optim	Math	2	2003-12-06 19:03
Probability of finding a factor in TF	eepiccolo	Math	4	2003-06-07 05:56
Probability of finding a factor in DC p-1	Deamiter	Math	4	2002-12-25 06:06
Probability of finding a prime number	Deamiter	Software	4	2002-10-11 16:36

2004-06-22, 23:36	#2
JuanTutors Mar 2004 3×167 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 2⁵×3 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:33	#7
Axel Fox May 2003 2⁵×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, 06:19	#10
markr "Mark" Feb 2003 Sydney 3×191 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!