Computing p and q from private key 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!
 A: 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$.
A: If the public exponent $e$ was calculated as $e=d^{-1}\mod{\phi(n)}$ you probably simply found secret exponent $d$ as denominator of fraction $\frac{k}{d}$, which is the one of convergents for contuned fraction $\frac{e}{n}$ (This is simplified Wiener's attack assuming use of Euler's totient function when generating inverse exponent). In this case use the probabilistic algorithm mentioned in the answer above. The underlying mathematics of it was described in A Further Weakness In The Common Modulus Protocol For The Rsa Cryptoalgorithm article.
In case of using Carmichael function $\lambda(n)$ to calculate public exponent, i assume you had to follow the complete algirthm which Wiener showed in his article Cryptanalysis of Short RSA Secret Exponents. If so, you do not need the above probabilistic algorithm, because following the complete Wiener's algorithm you had to calculate both intermediate guess of $\frac {p+q} {2}=a$ and guess of $\frac {p-q} {2}=b$. Having the latter two you can get factors of $n$ by calculating: $q=a-b$ and $q=a+b$. In other words Wiener's attack on RSA also gives factorization. See the formulas (31) and (32) in Wiener's article and his example.
