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")?

  • 1
    $\begingroup$ how would you specify such a distribution, just wondering... $\endgroup$ – kodlu Apr 22 '16 at 10:51
  • $\begingroup$ 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. $\endgroup$ – Tal-Botvinnik Apr 22 '16 at 11:18
  • $\begingroup$ 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). $\endgroup$ – user94293 May 22 '16 at 22:45

On trail to follow, from Handbook of Applied Cryptography fact 3.7:

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.