3
$\begingroup$

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

  • 2
    Did you see this posting? http://math.stacke$x$cha$n$ge.com/questions/12328/rsa-fast-factorization-of-n-if-d-and-e-are-know2012-09-24

1 Answers 1

7

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