polynomial time in finding constituent prime factors of an integer

Question

If given an integer n = pq, p and q are primes, and a way of computing phi(n) in polynomial time is given. Can we also get the value of p and q in polynomial time? The answer is we can, but how? We can use the method given for finding phi(n) in polynomial time.

Edit:

sorry for causing people to argue, I changed co-prime to prime now. The original problem is solved, but I'm still curious if this conclusion has a general form, I mean if n actually equals to p * r * s * ....It should still be able to get the most basic primes in polynomial time. How to prove?

Answer 1

You have a system of two equations in two unknowns:

$$ n = pq \qquad \qquad \varphi(n) = (p-1)(q-1) $$

Answer 2

Hint: $p$ and $q$ are the roots of $X^2-(p+q)X+pq$ and for primes $p,q$ we have $\varphi(pq)=(p-1)(q-1)$.

Answer 3

If $p, q$ are coprime, $\varphi(pq) = \varphi(p)\varphi(q)$. The problem of finding the totient function is equivalent to factoring, and no one has found a polynomial time algorithm for that.

If $p,q$ are primes, $\varphi(pq) = (p-1)(q-1)$.

Answer 4

Hint $\ $ Knowing $\,\color{#c00}{c = pq},\,$ and $\, \color{blue}{\phi(pq)}= (p-1)(q-1)\,$ we know $\,\color{#0a0}b = p+q = \color{#c00}{pq}-1-\color{blue}{\phi(pq)}.\,$ Thus we know $\,\color{#0a0}{b = p+q}\,$ and $\,\color{#c00}{c = pq},\,$ so we can solve for $\,p,q\,$ as the roots of a known quadratic

$$(x-p)(x-q)\,=\, x^2 -(\color{#0a0}{p+q}) x +\color{#c00}{pq}\, =\ \overbrace{x^2 - \color{#0a0}b\,x + \color{#c00}c}^{\large \color{#0a0}b,\ \color{#c00}c\,\ { known}}$$