mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-10-07, 12:49   #1
gLauss
 
Nov 2014

2·3·5 Posts
Default 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 here. 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 https://en.wikipedia.org/wiki/Dickman_function first, I will use the same notations.
\Psi(x,B1) should be the number of B1-smooth numbers below x, similiar for \Psi(x,B1,B2) .
Assume n is prime and large, too.

So I need to calculate 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\}}.

The denominator should be (if Chebyshev bias is not considered) \pi(2nk_{max}+1) divided by \varphi(2n)=n-1 or around \frac{(2nk_{max}+1)}{(n-1)log(2nk_{max}+1)} or around \frac{(2k_{max}+1)}{log(2nk_{max}+1)}.

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 \Psi(k_{max},B1,B2) 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 2kp+1 will be prime, too. Any ideas? And if I consider Brent-Suyama extension, then I am completly lost...

PS: Reading the source code 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.

Last fiddled with by gLauss on 2020-10-07 at 12:57
gLauss is offline   Reply With Quote
Old 2020-10-07, 20:53   #2
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

32·151 Posts
Default

Another P-1 calculator is here:
https://github.com/preda/gpuowl/blob...m1/pm1prob.cpp

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

Last fiddled with by preda on 2020-10-07 at 20:55
preda is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help with probability distribution. Unregistered Information & Answers 13 2011-07-15 15:12
Probability of factor (TF) nuggetprime Math 2 2011-03-19 22:14
Probability of finding a factor JuanTutors Software 20 2004-09-26 09:47
What is the probability distribution for M42 ? dsouza123 Math 2 2004-06-02 02:16

All times are UTC. The time now is 22:31.

Tue May 11 22:31:32 UTC 2021 up 33 days, 17:12, 0 users, load averages: 2.72, 2.66, 2.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.