3
$\begingroup$

Let $p$ and $q$ be prime numbers and $\phi$ Euler's totient function. Is there an efficient way of computing $\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, that is not simply based on factoring $p-1$ and $q-1$?

Obviously, if $p$ and $q$ do not equal two, $p-1$ and $q-1$ are even and consequently their prime factorization is entirely different from the prime factorization of $p$ and $q$. Therefore I assume that no such shortcut exists.

Do I overlook something?

$\endgroup$
2
$\begingroup$

No, not efficiently, not in general. Suppose $p=2p'+1$ and $q=2q'+1$ where $p',q'$ are prime. Then factoring $pq$ is believed to be hard. (Indeed, these primes are known as safe primes, and factoring a product of two safe primes is believed to be hard.) However we have

$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$

If you could compute $\varphi(\varphi(pq))$ from $pq$ efficiently for $p,q$ of this form, then you could factor $pq$ efficiently for $p,q$ of this form. The reduction works as follows. Consider the quadratic function $f$ given by

$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$

We can compute the coefficients of $f$, as

$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$ $$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$

so you can use the quadratic formula to solve for the roots of $f$ and recover $p',q'$. From this the factorization of $pq$ can be recovered.

So, no, you are not overlooking anything. There is likely no efficient way to compute $\varphi(\varphi(pq))$ for arbitrary numbers $pq$ (unless factoring is easy).

$\endgroup$
1
  • $\begingroup$ Thanks for this extensive answer. This was very helpful! $\endgroup$
    – Philipp
    Aug 18 '20 at 20:45

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.