1

I have a quick question: My book asks me to show that if someone were to find that value of $\phi(pq)$ then they would be able to find out p and q.

Is this possible? I've seen many examples of finding p and q given $\phi(pq)$ and the value of pq. Is it possible to do this without knowing the value of pq?

edit: p and q are also prime

The Physics Student
  • 810
  • 1
    Are you really sure that the book does not implicitly assume $pq$ to be known as well? Because without that, the problem does not seem to be easy. You'd have to factor $\varphi(pq)$ and run through its divisors, checking for primality of each $d+1$ and the same for its complement. If the number is "bad", factoring it is quite hard by itself. If it is "good", then the sheer number of divisors starts to be a problem. – Ivan Neretin Nov 11 '15 at 20:03
  • It does not. It says(word for word) "Show that if a snoop were to find $\phi(pq)$, then he could also find p and q" There is not context either - its a stand alone question. Im thinking its a typo. – The Physics Student Nov 11 '15 at 20:06
  • 2
    Yes, but in cryptanalysis the attacker usually does know $pq$, since that's not a secret. So the book may well implicitly assume it's known, even if it doesn't say so. – David Schneider-Joseph Nov 11 '15 at 20:09
  • Adding to @Ivan Neretin comment the divisors $(d_1+1)$ and $(d_2+1)$ should have the same number of bits. This restricts the number of combinations. –  Nov 11 '15 at 22:53

0 Answers0