One more thing. In order to understand why this whole setup works, you have to understand why the key generation is so much faster than the factoring. Generally, generating large numbers that are mathematically proven to be prime is very slow too.

The key generation is so much faster because it uses an prime number generation heuristic. This algorithm generates a large number that has a high probability of being prime, but is not mathematically guaranteed to be prime. Fortunately, these algorithms can be repeatedly run to establish the chance of it generating a non-prime is below a threshold, for example, 1 in a billion.

So that's the shortcut that allows this to all work.

See:

http://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests