How do I compute Euler phi function efficiently for repeated prime factors?

Question

In RSA decryption problems, you have to compute $\phi(n)$ and then sometimes $\phi(\phi(n))$ quickly. For example, I had to compute $\phi(2^5)$ for one particular problem and it seems to me (for example in testing situations) that there has to be some kind of algorithm to calculate this since you can't just use the property that $\phi(x) = x-1$ for x prime.

Answer 1

According to this Wikipedia page, given any prime number $p$, $\phi(p^k) = p^{k-1} \cdot (p - 1)$, and given two coprime numbers $m$ and $n$, $\phi(m \cdot n) = \phi(m) \cdot \phi(n)$.

So, write the number's prime factorization as ${p_1}^{k_1} \cdot {p_2}^{k_2} \cdot \cdots$, and its totient is ${p_1}^{k_1 - 1} (p_1 - 1) \cdot {p_2}^{k_2 - 1} (p_2 - 1) \cdot \cdots$.

Answer 2

Find all prime factors of $n$, then compute

$$\phi(n) = n\prod_{p|n}(1-\frac{1}{p})$$

where the product is over $n$'s prime factors.