mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2004-06-21, 22:49   #1
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3×167 Posts
Default 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?
JuanTutors is offline   Reply With Quote
Old 2004-06-22, 23:36   #2
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3·167 Posts
Default

Should this be in the Programming or Math section instead?
JuanTutors is offline   Reply With Quote
Old 2004-06-23, 00:19   #3
marc
 
marc's Avatar
 
Jun 2004
UK

139 Posts
Default

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.
marc is offline   Reply With Quote
Old 2004-06-23, 01:11   #4
Axel Fox
 
Axel Fox's Avatar
 
May 2003

6016 Posts
Default

Actually your chance is

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

which is (using a calculator) roughly 9.31 %
Axel Fox is offline   Reply With Quote
Old 2004-06-23, 01:54   #5
marc
 
marc's Avatar
 
Jun 2004
UK

139 Posts
Default

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.
marc is offline   Reply With Quote
Old 2004-06-23, 02:19   #6
nfortino
 
nfortino's Avatar
 
Nov 2003

3·5·11 Posts
Default

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.
nfortino is offline   Reply With Quote
Old 2004-06-23, 02:33   #7
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default

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.
Axel Fox is offline   Reply With Quote
Old 2004-06-23, 04:14   #8
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

1101100012 Posts
Default

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
Kevin is offline   Reply With Quote
Old 2004-06-23, 05:43   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001001001002 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2004-06-23, 06:19   #10
markr
 
markr's Avatar
 
"Mark"
Feb 2003
Sydney

13×43 Posts
Default

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!
markr is offline   Reply With Quote
Old 2004-06-23, 08:00   #11
MrHappy
 
MrHappy's Avatar
 
Dec 2003
Paisley Park & Neverland

5·37 Posts
Default

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.
MrHappy is offline   Reply With Quote
Reply

Thread Tools


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

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

Thu Oct 29 23:49:30 UTC 2020 up 49 days, 21 hrs, 1 user, load averages: 2.17, 2.08, 2.02

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.