key generation in RSA cryptosystem: why it can be performed in polynomial time? 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$:


*

*Choose two very large random prime integers:
$p$ and $q$ such that $|pq|_2=k$

*Compute $n$ and $φ(n)$:
$n = pq$ and $φ(n) = (p-1)(q-1)$

*Choose an integer $e$, $1 < e < φ(n)$ such that:
gcd$(e, φ(n)) = 1$ 

*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.

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?
