2020-10-07, 12:49 | #1 |
Nov 2014
2^{3}×3 Posts |
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. should be the number of B1-smooth numbers below x, similiar for . Assume n is prime and large, too. So I need to calculate . The denominator should be (if Chebyshev bias is not considered) divided by or around or around . 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 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 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 |
2020-10-07, 20:53 | #2 |
"Mihai Preda"
Apr 2015
17·79 Posts |
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 |
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 |