4
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ how would you specify such a distribution, just wondering... $\endgroup$
    – kodlu
    Apr 22, 2016 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$ Apr 22, 2016 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, 2016 at 22:45

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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