# Is knowing the private key of RSA equivalent to the factorization of $N$?

Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems true as I know the public/private key pair. Can someone help me to prove this?

Please provide references so that I can read further into this subject.

-
If you know $e$, $d$ and $n$, you can efficiently factor $n$. Just knowing $d$ is not enough if $e$ is big. –  CodesInChaos May 6 at 6:44
@CodesInChaos Do you mean that knowing $(N,e,d)$ if $e$ is big, then we cannot still factor $N$? –  Alex May 6 at 8:17
Knowing $(N,e,d)$, including with big $e$, allows finding the factorization of $N$, by heuristic or deterministic methods pointed in Samuel Neves's nice answer. If $e$ is unknown but small, we can enumerate small values to find $e$, using $(x^d)^e\equiv x\pmod N$ for arbitrary $x$ such as 2 as a test of having reached the right $e$; and then are back to the same problem [reposted with fix]. –  fgrieu May 6 at 10:12

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$.
Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.
when we select $e,d$, generally speaking, if they should $e,d <\phi(N)$ ? –  Alex May 18 at 2:33