# Prime factorization knowing n and Euler's function

My task is to factorize $n$ knowing it has two factors and $\varphi(n)$. How can I do it?

-
The expression of $\varphi(n)$ for this specific case could help... – Raymond Manzoni Oct 27 '12 at 15:52

Assuming you mean $n=pq$ for distinct primes $p,q$, you know the values $pq$ and $(p-1)(q-1) = pq - p - q + 1,$ so you know $p+q$ as well. That is enough.

-

Let $n = pq$ for two distinct primes $p$ and $q$, and assume $n$ and $\phi(n)$ are known. Since $\phi(n) = (p - 1)(q - 1) = pq - p - q + 1$, we can compute $p + q = n - \phi(n) + 1$. So we know $pq$ and $p + q$. Now consider the following quadratic $f$: \begin{align} f(x) &= x^2 - (n - \phi(n) + 1) x + n \\ &= x^2 - (p + q) x + pq \\ &= (x - p)(x - q). \end{align} All coefficients of $f$ are known in the first line, so we can compute its roots, which are exactly $p$ and $q$, as shown in the last line.

-

It is very easy to prove that $\rm n$ can be factored in polynomial time given any multiple of $\rm \varphi(n),\:$ e.g. see Gary Miller: Riemann's hypothesis and tests for primality, 1976.

Note $\$ This fact was well-known to the discoverers of RSA. Indeed they mention it explicitly in section IX of the original 1978 paper on RSA, which is quite readable.

-