Generating the keys for the RSA cryptosystem in probabilistic polynomial time

Question

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.

Answer 1

Short version: All the cool kids are using Randomized Algorithm !

Boring version:

1. Any deterministic (part of a) crypto system can be broken ! [Goldwasser Micali]

2. 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.. :)

3. Primality checking with Rabin Miller (probabilistic) is way faster than AKS (deterministic)