Sander came out with a paper describing how to generate what he calls an RSA-UFO. Anoncoin then utilizes this and mentions that the paper proves that the probability that a randomly generated integer, x, that is divisible by at least two primes of bit size greater than or equal to one-third the bit size of x is about 0.16.

However, I see in the paper the theorem saying

Let ξ $\in (\frac{1}{3}, \frac{5}{12})$. Then the number of integers $\leq x$ that have two distinct prime factors $\geq x^ξ$ is $x(\frac{1}{2} \ln^2(\frac{1}{2ξ}) + O(\frac{1}{ln(x)}))$

Taking $O(\frac{1}{ln(x)})$ as about 0 (since it approaches 0 as x grows), I see that the probability should be

$$\frac{1}{2} \ln^2(\frac{1}{2ξ}) \approx 0.082$$

when $ξ = \frac{1}{3}$, which should give a prime bit size of one-third the bit size of x. I do notice that I am off by a factor of about two, but it seems to me that that $\frac{1}{2}$ is necessary.

Where does the 0.16 probability come from, and where am I going wrong?

EDIT: I am wondering if I am not including the fact that generating random numbers with a particular bit size ensures the first bit is 1, which reduces the possible generated numbers less than x by half, about doubling the probability?



You must log in to answer this question.

Browse other questions tagged .