Quoth: "Adam P. Goucher"

...

Cryptographic keys must be generated using true randomness, and a lot of entropy worth of it, say 2000 bits worth.

If there are n possible birthdays of equal probability, then the number of people required for there to be a reasonable probability of shared birthdays is O(sqrt(n)) -- for reasons based on Stirling's formula. Hence, if we have Np? possible prime numbers that a random number generator could produce, where N is a reasonably large number (10^6, or so) and p is the number of people using this system, then there should be no intersection.

Based on the current word population, 90 bits of randomness should be ample to avoid collisions, not 2000.

Unfortunately you're not just trying to avoid collisions. I'm sure we have some real number theorists on the list, who can turn my fluffy statement into something closer to the truth but I'm pretty sure that if you know half of the digits of each of the factors, then you can factor the composite. It might even be 1/3rd (but might be 2/3rds). For example, consider (Lenstra's?) Divisors in Residue Classes method of primality proving. (You prove a number prime by generating an exhaustive but empty set of proper divisors in a particular residue class.) So if all your entropy is squeezed into one end of the number (or middle, etc.), your number might be easily factorable. More concretely, consider nextprime(10^500+random(10^20)) * nextprime(10^500+random(10^20)) as a number with more than 90 bits of entropy, but absolutely useless as a RSA modulus. Phil