# An efficient way of calculating 𝜙(𝜙(p*q)) where p and q are prime

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?

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).

• Thanks for this extensive answer. This was very helpful! Aug 18 '20 at 20:45