# How often do hard-to-factor numbers occur?

[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.

• You might find this question to be interesting. Commented Mar 19 at 1:06
• This seems more like a question in number theory than cryptography, how many semiprimes are there in some range whose smallest factor is bigger than some bound and the factors aren't too close. Are there any more significant requirements I'm missing? Commented Mar 19 at 3:24
• What do you exactly mean with "hard-to-factor"? Is it enough to find one prime factor of the given number to be not "hard-to-factor" or does one need to find all prime factors? Commented Mar 19 at 7:56
• No individual number is "hard to factor". For any fixed number there exists a trivial factoring algorithm that simply outputs the factors. Hardness of factoring is only a meaningful notion relative to a distribution. Commented Mar 20 at 7:41
• Possibly useful theorem by Landau: the number of semiprimes to $x$ is $\sim\frac{x\ln\ln x}{\ln x}$. However, not all (distributions of) semiprimes are hard to factor (couterexample: $2p$ with $p$ prime), and not all hard to factor (distributions of) integers are limited to semiprimes (counterexample: $p\,q\,r$ with $p$, $q$, $r$ random primes of equal bit size).
– fgrieu
Commented Mar 20 at 9:51

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.)

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.

• Integers that are easy to factor are primes - this isn't true, right? Commented Mar 20 at 20:52
• it is. primality testing can be done in polynomial time. Commented Mar 22 at 5:16
• @OscarSmith Which algorithm does primality testing faster for primes as compared to composites? Commented Mar 22 at 22:01
• Primality testing is quite fast for all integers (“quite fast” compared to usual cryptographic operations, obviously it’s much faster for even numbers for example). And if a number is found to be a prime, there you have its complete factorisation. Commented Mar 23 at 21:00
• That was a list of easy to factor integers. Easy to factor integers are A, B or C. In plain old English, if you change this to “easy to factor integers are A” is nonsense. Commented Mar 26 at 4:47

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} 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".