I was talking to a friend of mine yesterday about encryption. I was explaining RSA and how prime numbers are used - the product $N = pq$ is known to the public and used to encrypt, but to decrypt you need to know the primes $p$ and $q$ which you keep to yourself. The factorization of $N$ is the hard part, and that's why RSA is safe.
Then I was asked: Who actually calculates these primes, and how? They're huge, so can you do it on just a normal computer (in reasonable time)? And if not, and encryption software gets the primes from somewhere else, this third party would have a list of primes (however large) to try to factor $N$ with. Using it would be considerably easier than just brute forcing, trying to divide with every prime number up to $\sqrt{N}$. If they (or someone else) has the list, encryption isn't really safe.
So, how is it actually done?
They are generated on the machine doing the encryption. Generating primes of a given size is fairly easy, and verifying that they are prime can be done much faster than trial division.
1024-bit RSA requires two 512-bit primes. On my (old) machine it takes about 34 milliseconds to generate a 512-bit prime (so generating the whole key would take about 0.07 seconds). That's about 10 milliseconds to find the prime and 25 to verify it to high certainty. If I was willing to live with 'only' one mistake in $10^{100}$ I could verify a prime in a third the time. If I wanted to instead prove that it was a prime, it would take about 1.6 seconds... but that's overkill for reasonable purposes. (Better to move to a higher bit level with less certainty.)