Generating the keys for the RSA cryptosystem in probabilistic polynomial time In general every public key cryptosystem ``has'' a probabilistic polynomial time algorithm $G$ such that $G(1^k)=(\textrm{public key}, \textrm{private key=trapdoor})$; $G$ is called the key generator. Now for the RSA cryptosystem the keys, can be found in the following way:


  Bob decides the key length $k$, then $G(1^k)=((n,e), d)$ where $n=pq$
  with $p$ and $q$  prime numbers, $n$ has length $k$ (as bit string),  and $e\in\mathbb
 Z^\ast_{\phi(n)}$. The two primes $p$ and $q$  and are chosen in a
  random way, $\phi(n)$ is simply $(p-1)(q-1)$, $e\in\mathbb
Z^\ast_{\phi(n)}$ is randomly chosen and finally $d$ is calculated  in
  polynomial time with the extended Euclid algorithm. The couple $(n,e)$
  is setted as  the public key, whereas $d$ is the secret key.


I don't understand why this algorithm has probabilistic polynomial running time. Who ensures that I can find two random primes and $e$ in a reasonable time?

thanks in advance.
Short version: All the cool kids are using Randomized Algorithm ! 

Boring version:


Any deterministic (part of a) crypto system can be broken !  [Goldwasser Micali]
Primes density is pretty high (higher than one intuitively expects) as we talk of big numbers. Prime No. Theorem : #of primes between $1$ and $x$, $\pi(x) = \frac{x}{ln(x)}$ , So if randomly picking no.s usually means you have a fairly high chance of getting a prime.. :)
Primality checking with Rabin Miller (probabilistic) is way faster than AKS (deterministic)