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

$\endgroup$
1
  • $\begingroup$ All you need is to plug the $p$ you got into $2N=2pq$. Then you get a quadratic in $q$. $\endgroup$
    – N. S.
    Dec 5, 2012 at 20:33

1 Answer 1

Reset to default
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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}$ $\endgroup$
    – gfppaste
    Dec 5, 2012 at 22:31
  • $\begingroup$ You can use the quadratic formula to solve this equation $\endgroup$
    – Amr
    Dec 5, 2012 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.