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:
- $\phi(n) = (p-1)(q-1) = pq - p - q + 1$
- Solving for $p+q = pq - \phi(n) + 1$
- Take $(p-q)^2 = p^2 - 2pq + q^2$
- Solve $(p-q) = \sqrt{p^2 -2pq + q^2}$
- 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)$