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

Question

I want to determinate $p$ and $q$ in RSA.

I know that $n = 172451$ and $\phi(n) = 171600$.

$$171600 = pq - (p+q) + 1 = 172451 -(p + q) + 1$$ $$p + q = 172451-171600+1 = 852$$ $$(p-q)^2 = (p+q)^2-4pq = (852)^2 - 4(172451) = 36100$$

Now I'm stuck at this point and don't understand how can I get $p$ and $q$.

Anyone cares to explain.

P.S. - I've already looked at some other answers posted here on math.stackexchange.com but didn't unsertand

Answer 1

You are almost finished. We have $(p-q)^2=36100$. Without loss of generality we may assume that $p\ge q$. So $p-q=190$ (we took the square root).

We now know $p+q$ and $p-q$. By adding, we find $2p$ and hence $p$.

Answer 2

You know \begin{equation*} p q = n \end{equation*} and \begin{equation*} \varphi(n) = (p-1)(q-1) = pq - p - q + 1 = n - (p+q) + 1. \end{equation*} So \begin{equation*} p + q = n + 1 - \varphi(n). \end{equation*}

Now recall that in a quadratic equation \begin{equation*} x^2 - b x + c = 0, \end{equation*} the coefficient $b$ is the sum of the two roots, and $c$ is their product. It follows that you can find $p$ and $q$ as the roots of the equation \begin{equation*} x^2 - (n + 1 - \varphi(n)) x + n = 0. \end{equation*}