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?
Thanks for any advice.
 A: 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.
A: 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.
A: 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.
A: Well, we have it that:
$x^2 - (p+q)x + pq$
This is in the form of a quadratic equation. Notice the similarities to the standard quadratic equation that we learned about in high school:
$ax^2 + bx + c \; = \; 0$
Again, like we learned in high school, you can solve for $x$ by using the quadratic formula:
$x \; = \; \frac{-b\pm\sqrt{b^2-4ac}}{2a}$
Where in this case:
$a \; = \; 1$
$b \; = \; p+q \; = \; n-\varphi(n)+1$
$c \; = \; p q \; = \; n$
Ergo, we have:
$p \; = \; \frac{(p+q) + \sqrt{(p+q)^2 - 4pq}}{2}$
