mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Probability of factor (TF) (https://www.mersenneforum.org/showthread.php?t=15415)

 nuggetprime 2011-03-18 20:11

Probability of factor (TF)

Hi,
Is there a formula / excel spreadsheet anywhere which lets me calculate the probablility that I find a factor for Mn by trial factoring from x to x+1 bits, with no previously known factor?

Thanks,
nugget

 Mini-Geek 2011-03-18 21:28

[url]http://mersenne-aries.sili.net/credit.php[/url] (put in a TF assignment and factoring range, as part of the result it says the chance of finding a factor)
That's the easiest way, since it applies the formula for you.
The actual formula is at:
[url]http://www.mersenne.org/various/math.php[/url]
[quote]the chance of finding a factor between 2[sup]X[/sup] and 2[sup]X+1[/sup] is about 1/x[/quote]
Pretty simple. :smile:
But note that this only counts starting at about log_2(p) bits, since all factors must be of the form 2kp+1.

Whether there is a previously known factor does not make a difference in the distribution of further factors, but the TF depth does.

 Mr. P-1 2011-03-19 22:14

[quote]the chance of finding a factor between 2X and 2X+1 is about 1/x[/quote]

That only applies if no prior factoring work has been done, which could have found a factor in that range. If that isn't the case, for example if a P-1 test has been done on the exponent, then the probability of finding a factor with TF will be less.

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