Let $N < 2^a$ be a positive integer chosen uniformly at random. Let $\tilde{N}$ be the result of removing from $N$ all its prime factors less than $2^b$. What is the probability that $\tilde{N}$ is composite and $\tilde{N} > 2^c$?


The problem is similar to [Integers with a large smooth divisor](https://pdfs.semanticscholar.org/d48d/d2229998b82b00d27a65d8dac70012c3ed91.pdf) with "smooth divisor" replaced by "[rough](https://en.wikipedia.org/wiki/Rough_number) composite divisor".


**Motivation**


I want to build the smallest-possible safe RSA modulus without a trusted party. A positive integer is a **safe RSA modulus** if, after removing all its prime factors less than 512 bits, it is composite and has size at least 2048 bits.


(That is we set $b=512$ and $c=2048$ in the above problem. The parameter $b=512$ protects against the [ECM](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization) which has found primes of size [up to 273 bits](https://members.loria.fr/PZimmermann/records/top50.html). The parameter $c=2048$ protects against the [GNSF](https://en.wikipedia.org/wiki/General_number_field_sieve) which factored numbers up to 768 bits.)


The strategy is to randomly sample several random numbers $N\_1, ..., N\_k$ and multiply them together. Each $N\_i$ has some probability $p$ of being a safe RSA modulus so the product $N\_1...N\_k$ has probability $1 - (1-p)^k$ of being safe.


To choose $k$ appropriately I need a reasonably tight lower bound for $p$. (The above strategy of multiplying randomly chosen integers was [pioneered by Thomas Sanders](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.4015&rep=rep1&type=pdf) but he used a different—unnecessarily strict—definition of a safe RSA modulus.)



Density of integers with a large rough divisor
If $a/b$ is not too large, you can compute the probability using arguments as in the computation leading to the asymptotics for smooth numbers. In theory, you can compute for all $\beta, \gamma$ a real number $\rho$, such that 
$$
\#\{n\leq x: \tilde{n}>x^\gamma\} \sim \rho x,
$$
where $\tilde{n}$ is $n$ divided by all prime divisors $p$ of $n$ satisfying $p\leq x^\beta$. Unless $(\beta, \gamma)$ are in some stupid range, e.g. $\gamma>1$, $\rho$ will be positive. Your range $a=4096, b=512, c=2048$ should be manageable, but might take days to weeks of work.


Let me explain the computations at the easier example $\beta=0.3$, $\gamma=0.7$. 


All prime divisors of $\tilde{n}$ are larger than $x^{0.3}$, thus there are at most 3 of them. As you require that $\tilde{n}$ is composite, there are 2 or 3 prime factors. Suppose first there are exactly 2 of them. The number of integers $n<x$, such that $\tilde{n}=pq$ equals $\Psi(x/pq, x^{0.3})$, where $\Psi(x,y)$ is the number of integers $n\leq x$ with all prime factors $\leq y$. Thus, the total number of integers, such that $\tilde{n}>x^\gamma$ and $\tilde{n}$ has exactly 2 prime divisors is
$$
\underset{x^{0.7}<pq}{\sum\_{p, q>x^{0.3}}} \Psi\left(\frac{x}{pq}, x^{0.3}\right)\sim
\underset{x^{0.7}<pq<x}{\sum\_{p, q>x^{0.3}}}\rho\left(\frac{\log(x/pq)}{0.3\log x}\right)\frac{x}{pq}\sim\underset{s, t\geq 0.3}\int\limits\_{0.7\leq t+s\leq 1}\rho\left(\frac{1-t-s}{0.3}\right)\frac{ds\;dt}{st},
$$
where $\rho$ is the Dickman function. The Dickman function is continuous and diferentiable at all places different from 1 with rather small derivative, thus the right hand side can be computed numerically without much pain.


Similarly, the case of 3 prime factors leads to the integral
$$
\underset{0.7\leq s+t+u\leq 1}{\int\limits\_{s, t, u>0.3}}\rho\left(\frac{1-t-s-u}{0.3}\right)\frac{ds\;dt\;du}{stu}.
$$
In the range of integration $1-s-t-u<0.3$, thus the argument of the Dickman function is $<1$, and the value of the function is constant 1. Similarly, the lower bound $s+t+u\geq 0.7$ is trivially satisfied. Thus we get
$$
\underset{s+t+u\leq 1}{\int\limits\_{s, t, u>0.3}}\frac{ds\;dt\;du}{stu},
$$
which is even easier.


As $\beta$ gets smaller, the dimension of the range of integration increases, but something like $\beta=\frac{1}{6}$ or $\frac{1}{8}$ should still be doable. The problem is that for higher dimension the polyhedron over which integration takes place is pretty complicated, so Monte-Carlo methods will probably not help too much either. 


In general convergence to the asymptotics is rather slow, but for $x=2^{4096}$ the error should already be pretty small. 


