key generation in RSA cryptosystem: why it can be performed in polynomial time?

Question

Suppose that I want to generate the keys of the RSA cryptosystem: the public key will be the couple $(n,e)$ where $n$ is the product of two primes $p$ and $q$ and gcd$(\phi(n),e)=1$.The private key will be the integer $d$ such that $ed=1$ (mod $\phi(n)$). Suppose that the length of $n$ (represented as bit string) is $k$, therefore the following is an algorithm that outputs $n$, $e$ and $d$:

1. Choose two very large random prime integers: $p$ and $q$ such that $|pq|_2=k$
2. Compute $n$ and $φ(n)$: $n = pq$ and $φ(n) = (p-1)(q-1)$
3. Choose an integer $e$, $1 < e < φ(n)$ such that: gcd$(e, φ(n)) = 1$
4. Compute $d$, $1 < d < φ(n)$ such that: $ed ≡ 1$ (mod $φ(n)$)

I have showed that points 1,2,4 can be computed in polynomial time of $k$, but I can't find any algorithm that can compute the point 3 in polynomial time.

Do you have any idea about it?

Edit: I'm wrong about the fact that the point $1$ can be performed in polynomial time. I had in my mind a wrong brute force argument. In an answer above, the user @TonyK says that this is an open problem.

Answer 1

The primorials grow as $m^m$, so less than $k$ of them will be less than $n$. At least one of the first $k+1$ primes will not divide $\phi(n)$ Can you sieve the first $k$ primes in polynomial time?

Answer 2

Step 1 is the hard one! I think that it still hasn't been proven to be polynomial, although it is believed to be.

Step 3 is easy, if all you need is an $e$ such that $(e,\phi(n)) = 1$ (although a real-life public key protocol will require more than this). Just let $e$ be the smallest prime that doesn't divide $\phi(n)$. This is clearly polynomial in $\log_2(n)$.