I'm trying to estimate the probability that Pollard's p-1 factorization in its two-stages variant finds a factor of an RSA modulus product of $k$ random $b$-bit primes, as a function of the bounds $B_1$ and $B_2$ used.
That's about $1-(1-P)^k$, or about $k\,P$ for low $P$, where $P$ is the probability that a $b$-bit prime $p$ has $p-1$ with its largest prime factor less than $B_2$ and its second-largest prime factor less than $B_1$.
My (incorrect) idea was that we must have $P\ge\rho\Bigl(\frac{b-1}{\log_2(B_2)}\Bigr)\rho\Bigl(\frac{\log_2(B_2)}{\log_2(B_1)}\Bigr)$ where $\rho$ is Dickman's function [*], on the assumption that $p-1$ behaves like a random even integer, that the probability of the largest prime factor $q$ being less than $B_2$ is about $\rho\Bigl(\frac{b-1}{\log_2(B_2)}\Bigr)$; and then the conditional probability of the second-largest prime factor being less than $B_1$ is about $\rho\Bigl(\frac{\log_2(q)}{\log_2(B_1)}\Bigr)$, which is at least $\rho\Bigl(\frac{\log_2(B_2)}{\log_2(B_1)}\Bigr)$.
Problem is, my estimate is much larger than the one given by gmp-ecm with option -pm1 15e9
[#] which estimates its own probability of success as:
Using B1=15000000000, B2=19849281594647716 (..)
Probability of finding a factor of n digits (assuming one exists):
20 25 30 35 40 45 50 55 60 65
0.84 0.58 0.32 0.15 0.063 0.023 0.0078 0.0024 0.00068 0.00018
For $n=65$ decimal digits, that is $b=216$, I get $P$ at least $0.0028$, which is over 15 times more than ECM's estimate $0.00018$.
What's the cause of that discrepancy?
[*] Dickman's function $\rho$ is defined for $u\in\mathbb R^+$ by $$\begin{cases} \rho(u)=1 & \text{if }0\le u\le1\\ \rho(u)=1-\int_1^u\rho(t-1)/t\;dt& \text{if }u>1 \end{cases}$$ As $B$ grows, the probability that a random integer about $B^u$ has all its prime factors less than $B$ converges to $\rho(u)$. Sometime it is considered Dickman's function $F$ defined by $F(\alpha)=\rho(1/\alpha)$. In particular, Richard P. Brent's Some Integer Factorization Algorithms using Elliptic Curves uses $\rho$ for that $F$.
[#] gmp-ecm with option -pm1
implements Peter L. Montgomery and Alexander Kruppa's Improved Stage 2 to P±1 Factoring Algorithms, in proceedings of ANTS 2008. The first parameter is $B_1$. $B_2$ is chosen automatically if not specified as second parameter.