# Proof of discovering two large prime numbers in polynomial time

$N=p*q$ is a product of two distinct primes. Show that if $\phi(N)$ and 2N are known, then it is possible to compute p and q in polynomial time.

so, I know that $\phi(N)=(p-1)(q-1)$

Given this, if $\phi(N)=C$ where $C$ is a known constant,

$C=(p-1)(q-1)$

$\frac{C}{q-1}+1=p$

So, I know it is possible to compute p and q. How would I prove that it is possible to compute them in polynomial time?

-
All you need is to plug the $p$ you got into $2N=2pq$. Then you get a quadratic in $q$. –  N. S. Dec 5 '12 at 20:33
$\phi(N)=(p-1)(q-1)=pq-(p+q)+1=N+1-(p+q)$, thus: $$p+q=N+1-\phi(N)$$ $$pq=N$$ You have two equations that will enable you to solve for p,q using the quadratic formula
So to me, this reduces to $p=\frac{1-2q}{2}$, thus $N=q\bigg(\frac{1-2q}{2}\bigg)$... How would I put this in quadratic form? All I can reduce this to is $N=\frac{-2q^2+q}{2}$ –  gfppaste Dec 5 '12 at 22:31