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

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

-

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$.

-
Hi. Something like $\frac{852+190}{2} = 521$ So $p = 521$ and $q = 331$? –  Favolas Jan 15 '13 at 19:33
Yes, that's it. As you can see, you were almost there. –  André Nicolas Jan 15 '13 at 19:35
Sweet. Many thanks :) –  Favolas Jan 15 '13 at 19:36
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*}