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.