View Single Post
2003-05-09, 02:53   #4

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Re: Probability of finding a factor in TF

Quote:
Originally Posted by eepiccolo
At http://www.mersenne.org/math.htm, we are told:
Quote:
 the chance of finding a factor between 2^x and 2^x+1 is about 1/x.
First, let's note that the sentence begins with "Looking at past factoring data we see that the chance ..." Right now I don't recall whether I've seen a proof of that estimate. Judging by the sentence's wording, it may be an empirical observation.

Quote:
 My question is this: is this probability dependent or independent of whether or not other factors have been found?
If I understand correctly, what is meant is "... the chance that 2^p-1 has a factor between 2^x and 2^(x+1) is approximately 1/x."

That is, it refers to the probability of the existence of a factor (known or unknown) of 2^p-1 within the specified range, not necessarily the probability of discovering a previously-unknown factor there after some factors of 2^p-1 are already known.