# 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?

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.

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