Recommended Key Size

1024-bit keys imply roughly 512-bit primes, or 153-decimal digit primes, of which there are about 10150 (compared to 1073 particles in the universe).

Of course the problem is not to find a prime at random. The problem is to factor a known number. Very large numbers HAVE been factored by computers. Look here for a description of how a very large RSA number (product of two large primes) was factored in 5000 mips years by distributed computing (600 volunteers in 20 countries).

Here's the 128 digit number that was factored:

114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
It turns out that this is:
3490529510847650949147849619903898133417764638493387843990820577 *
          32769132993266709549961988190834461413177642967992942539798288533
Which would have been my guess, too.

For asymmetric or public key lengths, (cryptology expert) Bruce Schneier recommends 1280 bits through 2005 for individuals, 1536 for corporations, and 2048 for governments.

If you want your key to last longer, ...