1
$\begingroup$

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

  • 0
    All you need is to plug the $p$ you got into $2N=2pq$. Then you get a quadratic in $q$.2012-12-05

1 Answers 1

4

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

  • 0
    You can use the quadratic formula to solve this equation2012-12-05