If $n = p_1 p_2$ for primes $p_1 \ne p_2$, $\phi(n)$ is $\phi(p_1)\cdot\phi(p_2)$. Does that mean that the possible range of $\phi(n)$ is somewhat narrow, that $(p_1-1) \cdot (p_2-1)$ (that is, $\phi(n)$) is close to $p_1\cdot p_2$ (that is, $n$)?


$n - \phi(n) = p + q - 1$. $p$ and $q$ are secret uniform random 1024-bit prime numbers. Is a difference of near $2^{1024}$ ‘close’?

  • $\begingroup$ what I mean is, phi(n) should be much much closer to n than to 0? $\endgroup$ – asterism May 22 '19 at 17:33
  • 1
    $\begingroup$ Well, what's your metric and what do you consider close? The absolute distance from $\phi(n)$to $n$ is $p + q - 1 \approx 2^{1024}$; of course, $n$ and $\phi(n)$ are near $2^{2048}$, so, in that sense, yes, $\phi(n)$ is closer to $n$ than to $0$. $\endgroup$ – Squeamish Ossifrage May 22 '19 at 17:37
  • $\begingroup$ largest difference would be if either prime is 2 then I guess $\endgroup$ – asterism May 22 '19 at 17:49
  • $\begingroup$ If either prime is 2, then you are in trouble for RSA! $\endgroup$ – Squeamish Ossifrage May 22 '19 at 17:50
  • $\begingroup$ yes but, like, I mean, largest difference would be if either prime is as small as possible? or, what you said is exactly that, so if 2 does not work would you not have to adjust the range you gave? $\endgroup$ – asterism May 22 '19 at 17:52

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.