How often do hard-to-factor numbers occur?

Question

[Computer scientist here who is not totally familiar with the factoring literature -- please forgive my ignorance.]

It's well known that hard-to-factor integers, $n$, are typically semi-primes, such that their factors are roughly $O(\sqrt{n})$ in size. However, it's not clear to me that all such semi-primes are necessarily hard (maybe there are algorithms which succeed on some, but not all such instances).

My question is, if I enumerate through the integers $1,2,3,...$ etc., how frequently do these hard-to-factor instances occur? I'm interested in both the case where we are only concerned with semi-primes, but also any other hard-to-factor cases, and how frequently they occur. Is it true that all semi-primes with $\sim O(\sqrt{n})$ factors are hard to factor?

I would be particularly interested to know if I can take an interval of intergers $[2^k, 2^k + p(k)]$ for some sufficiently large polynomial $p$, for each $k\in \mathbb{N}$, such that I'm highly likely to run into $poly(k)$-many hard instances. Or equivalently, given an interval $[x, x + w]$ for some $w$, can I lower-bound the number of hard instances I expect to find?

Edit: More generally, given an integer $k$ is there a way of selecting selecting $poly(k)$ many integers with values between $(2^k, 2^{k+1})$ which are hard to factor*. The case above for $[2^k, 2^k + p(k)]$ would give an example of this, as one could state at $2^k$ and simply enumerate up to $2^k+poly(k)$ and we would get a set of integers, which (hopefully) at least $poly(k)$ many would be hard-to-factor.

*If necessary, we can allow that this occurs with high probability.

Answer 1

As I commented already, the easier problem of finding many hard-to-factor numbers in the (big) interval $[2^k, 2^{k+1}]$ is relatively easy, as this is exactly what an RSA key generation has to do: The bitlength $k$ is given as input, and a hard-to-factor modulus is given as part of the output. The density of the possible moduli returned by an RSA key generation in your interval $[2^k, 2^{k+1}]$ is about $\frac{1}{(k\cdot\log{2})^2}$, if it does not artificially restrict the choice randomly generated prime factors beyond taking them of the same bitlength.

(Asking first for an interval of polynomial size made your question quite hard, as a random prime of bitlength $\frac{k}2$ is extremely unlikely to have a multiple contained in this small interval.)

Answer 2

Integers that are easy to factor are primes, integers with small factors, where you can remove all small factors and the remaining number is easy to factor. Plus special cases, like semi primes that are the product of two numbers that are close together.

It’s not very difficult to find a prime factor p in $\sqrt p$ steps (that’s what I know how to do, but I know there are better algorithms). Assuming that $10^9$ steps are doable you can find prime factors up to $10^{18}$. And primality testing is easy. So if x is a prime or an almost square number or some other special case, or the product of primes up to $10^{18}$, or the product of two such numbers, then it is easily factorable.

Answer 3

If we define "hard to factor" numbers as semi-primes with both factors greater than $2^{\frac k4}$. The average prime gap at this size is < $k\ln(2)$, so for each prime $p_1$ in $[2^{\frac k4}, 2^{\frac k2}]$, the chance of their being a prime $p_2 $ such that $p_1\cdot p_2$ is in $[2^k,2^k+w]$ is roughly $\frac w{p_1k\ln(2)}$.

To sum this probability up by $p_1$ we can break our $p_1$s up into buckets from $2^{r}<p<2^{r+1}$ for $r$ in $[\frac k4, \frac k2 -1]$. For each $r$ we get $\frac{2^{r}}{k\ln(2)}$ possibilities for $p_1$, yielding an average of $\frac w{2k\ln(2)}$ combinations of $p_1$ and $p_2$ for each $r$.

Summing over the $\frac k4$ values for r, we get a value greater than $\frac {w}{8k\ln(2)^2}$.

Note that the difference between this answer and @garfunkel's is that my answer uses a looser definition of "hard to factor".