Density of integers with a large rough divisor

Question

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 with "smooth divisor" replaced by "rough 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 which has found primes of size up to 273 bits. The parameter $c=2048$ protects against the GNSF 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 but he used a different—unnecessarily strict—definition of a safe RSA modulus.)

Answer 1

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.