Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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 '14 at 6:44
@CodesInChaos Do you mean that knowing $(N,e,d)$ if $e$ is big, then we cannot still factor $N$? – T.B May 6 '14 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 '14 at 10:12
up vote 7 down vote accepted

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

share|improve this answer
when we select $e,d$, generally speaking, if they should $e,d <\phi(N)$ ? – T.B May 18 '14 at 2:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.