RSA solving for $p$ and $q$ knowing $\phi(pq)$

Question

I am trying to find primes $p$ and $q$ in the RSA algorithm given $n = pq$ and the value of $\phi(n)$. I know the following:

1. $\phi(n) = (p-1)(q-1) = pq - p - q + 1$
2. Solving for $p+q = pq - \phi(n) + 1$
3. Take $(p-q)^2 = p^2 - 2pq + q^2$
4. Solve $(p-q) = \sqrt{p^2 -2pq + q^2}$
5. Simplify to $(p-q) = \sqrt{p^2 + 2pq -4pq + q^2} = \sqrt{(p+q)^2 -4pq}$

Now we can solve for $p$ and $q$:

$p = \dfrac{(p+q) +(p-q)}{2}$ and $q = \dfrac{(p+q)-(p-q)}{2}$

Is there a better or faster way to solve for $p$ and $q$ given $pq$ and $\phi(pq)$

Answer 1

There is, based on the simple fact that $$(X-p)(X-q)=X^2-2\frac{p+q}{2}X+pq.$$

All you need to do is compute $\displaystyle m=\frac{p+q}{2}=\frac{n-\phi(n)+1}{2}$, then $$p,q=m\pm\sqrt{m^2-n}.$$