Computing p and q from private key

Question

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is there a way to calculate p and q from this information? If so, any links and explanation would be much appreciated!

Answer 1

If it is valid RSA, then $ L = ed-1$ is a multiple of the Carmichael function $\lambda(n) = \mathrm{lcm}(p-1, q-1)$.

In the solutions to exercise 18.12 (ii) from J. v. zur Gathen, J. Gerhard, Modern computer algebra Modern computer algebra, 2nd ed. (2003), you find ALGORITHM 18.16 Special integer factorization. This randomized algorithm computes the set of prime divisors of an squarefree odd integer $N \ge 3$, given a multiple $L \in \mathbb{N}$ of $\lambda(N).$

You can get the solution manual to selected exercises from the authors site, it includes the pseudo code for Alg. 18.16.

If you are using CRT-RSA you can recover p,q from n,e,dp (dp is CRT exponent of p) by an algorithm from S. Maitra, S. Sarkar: Polynomial-Time Equivalence of Computing the CRT-RSA Secret Key(s) and Factoring (http://eprint.iacr.org/2009/062)

Edit: As Jyrki Lahtonen suggested, here are the main ideas from MCA Algorithm 18.16:

Write $L=2^k m, k \ge 1$ with odd $m$. Choose a random $a \in [2,N-2]$. If $\gcd(a,N) \ne 1 $ you have found a factor by accident. Otherwise compute $b_0=a^m \pmod N$. If $b_0=1 \pmod N$, choose another $a$. Otherwise compute $b_{i+1} = b_i^2 \pmod N$ for $i=0\dots k$. Compute $g=\gcd(b_j,N)$ where $j$ is maximum index with $b_j\ne 1 \pmod N$. If $g\ne 1$ and $g \ne N$ it is a non-trivial factor, otherwise choose another $a$.