mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   P-1 factor probability distribution given n, B1 and B2 bounds (https://www.mersenneforum.org/showthread.php?t=26055)

gLauss 2020-10-07 12:49

P-1 factor probability distribution given n, B1 and B2 bounds
 
I want to calculate how likely a potential factors in a given bitrange will be missed by P-1, given B1, B2 and n. For ECM, I can get this information from [url=http://www.wraithx.net/math/ecmprobs/ecmprobs.html]here[/url]. It can't be the same as ECM for P-1, because P-1 will use the fact that the factor is of form 2kn+1.

Please read about the [url]https://en.wikipedia.org/wiki/Dickman_function[/url] first, I will use the same notations.
[TEX]\Psi(x,B1)[/TEX] should be the number of B1-smooth numbers below x, similiar for [TEX]\Psi(x,B1,B2)[/TEX] .
Assume n is prime and large, too.

So I need to calculate [TEX]p(n,B1,B2,k_{max}) = \frac{\left\{k\in\mathbb{N}|k<k_{max}\text{ and }2nk+1\in\mathbb{P}\text{ and }k\text{ is B1/B2-powersmooth}\right\}}{\left\{k\in\mathbb{N}|k<k_{max}\text{ and }2nk+1\in\mathbb{P}\right\}}[/TEX].

The denominator should be (if [url=https://en.wikipedia.org/wiki/Chebyshev%27s_bias]Chebyshev bias[/url] is not considered) [TEX]\pi(2nk_{max}+1)[/TEX] divided by [TEX]\varphi(2n)=n-1[/TEX] or around [TEX]\frac{(2nk_{max}+1)}{(n-1)log(2nk_{max}+1)}[/TEX] or around [TEX]\frac{(2k_{max}+1)}{log(2nk_{max}+1)}[/TEX].

However, I can't come up with a method to count the elements in the nominator, not even if I consider stage1 only. By definition there are [TEX]\Psi(k_{max},B1,B2)[/TEX] potential values for k where k will be power-smooth with B1/B2 bound, but I don't know how to count for how many of those [TEX]2kp+1[/TEX] will be prime, too. Any ideas? And if I consider Brent-Suyama extension, then I am completly lost...

PS: Reading the [url=https://github.com/shafferjohn/Prime95/blob/master/pm1prob.c]source code[/url] of Prime95, it seems that it the P-1 factor probability for a mersenne number is the same as the P-1 factor probability for a random number with n bits less. However, I do not yet see why this is.

preda 2020-10-07 20:53

Another P-1 calculator is here:
[url]https://github.com/preda/gpuowl/blob/master/pm1/pm1prob.cpp[/url]

Oh, I think the two are related or similar, so no new insights.


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.