If the public key $(e,n)$ and the private key $(d,n)$ are known, what is the easiest way to find the primes $p$ and $q$?

When $n$ and $\phi(n)$ are given this is easy to solve. But I can't manage it given just $(e,d,n)$.
Thanks for any help.

  • $\begingroup$ If you have $e$ and $d$, and you know that $ed \equiv 1 \pmod{\varphi(n)}$ - or $\mathrm{lcm}{(p - 1, q - 1)}$ - what can you deduce? $\endgroup$ – Thomas May 11 '14 at 19:26
  • $\begingroup$ Maybe that p-1 and q-1 are divisors of ed-1? @Thomas $\endgroup$ – Eryndis May 11 '14 at 19:39
  • 1
    $\begingroup$ I'm not sure I follow what you mean by "2 divides p - 1 ϕ(p-1) times", but the basic idea is this: if 2 divides $p - 1$, $x$ times, and 2 divides $q - 1$, $y$ times, then 2 divides $ed - 1$ at least $\max(x, y)$ times. So if you keep dividing $ed - 1$ by 2, at some point you will end up with a number that is a multiple of $p - 1$ but not of $q - 1$ (or vice versa). Then using Fermat's little theorem can produce a factor of $n$ (there are some details but that is essentially the idea). $\endgroup$ – Thomas May 11 '14 at 20:42
  • 1
    $\begingroup$ If you prefer, you can use the following idea: since $ed - 1$ is a multiple of both $p - 1$ and $q - 1$, if follows that $a^{\frac{ed - 1}{2^k}} \equiv \pm 1 \pmod{p, q}$ for some small $k$. Thus trying a bunch of random $a$'s, you will quickly find an $a$ which is a quadratic residue modulo $p$ but a quadratic nonresidue modulo $q$, such that $a^{\frac{ed - 1}{2^k}} - 1$ is a multiple of $p$ but not of $q$, and you are done. $\endgroup$ – Thomas May 11 '14 at 21:37
  • 2
    $\begingroup$ see my question Is knowing the private key of RSA equivalent to the factorization of N? $\endgroup$ – T.B May 12 '14 at 0:19

It's quite easy to find out the two primes $p$ and $q$ given the secret integer $d$ and the public modulus $n$ and the public exponent $e$.

An algorithm is found on the Appendix C of document SP800-56B.

I copy it here:

Appendix C: Prime Factor Recovery (Normative)

The following algorithm recovers the prime factors of a modulus, given the public and private exponents. The algorithm is based on Fact 1 in [Twenty Years of Attacks on the RSA Cryptosystem, D. Boneh, Notices of the American Mathematical Society (AMS), 46(2), 203 – 213. 1999. ].

Function call: RecoverPrimeFactors(n,e,d)


  1. n: modulus

2.e: public exponent

3.d: private exponent

Output:1.(p,q): prime factors of modulus

Errors: “prime factors not found”

Assumptions: The modulus $n$ is the product of two prime factors $p$ and $q$; the public and private exponents satisfy $de ≡ 1 \, (\mod \lambda(n))$ where $λ(n) = LCM(p– 1,q– 1)$


  1. Let $k = de – 1$. If $k$ is odd, then go to Step 4.
  2. Write $k$ as $k= 2^tr$, where $r$ is the largest odd integer dividing $k$, and $t ≥ 1$.
  3. For $i=1 \dots 100$ do:

    a. Generate a random integer $g \in [0, n−1]$.

    b. Let $y = g^r \mod n$.

    c. If $y= 1$ or $y = n– 1$, then go to Step g.

    d. For $j \in [1, t– 1]$ do:

      I. Let $x = y^2 \mod n$.
      II. If $x = 1$, go to Step 5.
      III. If $x =n– 1$, go to Step g.
      IV. Let $y=x$.

    e. Let $x=y^2 \mod n$.

    f. If $x = 1$, go to Step 5.

    g. Continue.

  4. Output “prime factors not found” and stop.

  5. Let $p = \gcd(y– 1, n)$ and let $q = n / p$.

  6. Output $(p,q)$ as the prime factors.

| improve this answer | |
  • $\begingroup$ Before seeing your question, I was looking for the same algorithm and when I found the specification and wrote some python code to implement it and test. You'll find an improvable but working code here: gist.github.com/ddddavidee/b34c2b67757a54ce75cb $\endgroup$ – ddddavidee May 12 '14 at 7:23
  • $\begingroup$ $e$ is not supposed to be secret. $\;$ $\endgroup$ – user991 Aug 8 '14 at 8:03
  • $\begingroup$ yes, I agree, sorry I correct the answer. (thanks!) $\endgroup$ – ddddavidee Aug 8 '14 at 8:06
  • $\begingroup$ You can skip step 1. $\lambda(n)$ is even, $ed$ has to be odd, and $ed-1$ has to be even again. $\endgroup$ – tylo Aug 8 '14 at 13:05
  • $\begingroup$ @ddddavidee check my comment in your gist. Also thanks for sharing, I solved a CTF (id0-rsa.pub/problem/45) with your script :) $\endgroup$ – G0D0T Apr 24 at 15:54

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