My task is to factorize $n$ knowing it has two factors and $\varphi(n)$. How can I do it?
Thanks for any advice.
My task is to factorize $n$ knowing it has two factors and $\varphi(n)$. How can I do it?
Thanks for any advice.
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.