# 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?

• Basically, there are a lot of primes available to choose from. – Paŭlo Ebermann May 2 '14 at 20:12
• Yes this is the intuition, but is there a formal proof aof this? – Dubious May 2 '14 at 20:23
• – user991 May 2 '14 at 21:12

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.. :)
• "=" $\mapsto$ "$\approx$" $\;$ – user991 May 3 '14 at 5:15