RSA Public key-Prove that if any one of p,q,ϕ(n) is known, then you can quickly use it to find the other two as well.

Question

I'm a little confused as to how to go about this, I've read through the bottom answer to this question : RSA solving for $p$ and $q$ knowing $\phi(pq)$ and $n$ but in that question they find p and q after knowing phi(n) AND n. Any help would be appreciated, thanks.

Answer 1

Given $p$:

• $q=\frac{n}{p}$
• $\phi(n)=(p-1)(q-1)$

---

Given $q$:

• $p=\frac{n}{q}$
• $\phi(n)=(p-1)(q-1)$

---

Given $\phi(n)$:

• $p=\frac{(n-\phi(n)+1)+\sqrt{(n-\phi(n)+1)^2-4n}}{2}$
• $q=\frac{n}{p}$

Answer 2

Let's first look at the two easy cases. If you know either $p$ or $q$, then finding the other two are very easy given that $pq =n$ and $n$ is publicly known.

Given that you know $\phi(n)$, then the answer provided in the link you gave is a really clever way of finding $p$ and $q$.