# How to prove that an integer is hard to factorize when sampled from a known distribution

Suppose that an $n$-bit integer $c$ has been randomly drawn from a distribution $\chi$, whose description is known. Is there a general method to check if this particular sampling helps factorize $n$? Are there any results in this direction (i.e. results like "don't choose an RSA modulus whose factors were sampled with this or that distribution")?

• how would you specify such a distribution, just wondering... – kodlu Apr 22 '16 at 10:51
• Say, for instance, that you know that $p,q$ are sampled according to prime search near a Gaussian distribution... Or in my case, $p$ and $q$ bits are sampled using Bernoulli trials with low probability of being 1. – Tal-Botvinnik Apr 22 '16 at 11:18
• You can check the following paper: J. Brandt and I. Damgård. On generation of probable primes by incremental search. In Advances in Cryptology − CRYPTO ’92, vol. 740 of Lecture Notes in Computer Science, pp. 358–370, Springer, 1993. dx.doi.org/10.1007/3-540-48071-4_26 (DOI:10.1007/3-540-48071-4_26). – user94293 May 22 '16 at 22:45

Let $n$ be chosen uniformly at random form the interval $[1, x]$.
1. if $1/2 \leq \alpha \leq 1$, then the probability that the largest prime factor of $n$ is $\leq x^{\alpha}$ is approximately $1+ ln(\alpha)$. Thus, for example, the probability than $n$ has a prime factor $> \sqrt(x)$ is $ln(2) \approx 0.69$
2. The probability that the second-largest prime factor of $n$ is $\leq x^{0.2117}$ is about $1/2$.
3. The expected total number of prime factors of $n$ is $ln ln x + \mathbb{O}(1)$. (If $n = \prod p_i^{e_i}$, the total number of prime factors of n is $\sum e_i$.)