Are there any efficient algorithms for computing the [Euler totient function](http://en.wikipedia.org/wiki/Euler%27s_totient_function)? (It's easy if you can factor, but factoring is hard.)


Is it the case that computing this is as hard as factoring?


**EDIT**: Since the question was completely answered below, I'm going to add a related question. How hard is it to compute the number of prime factors of a given integer? This can't be as hard as factoring, since you already know this value for semi-primes, and this information doesn't seem to help at all. Also, determining whether the number of prime factors is 1 or greater than 1 can be done efficiently using Primality Testing.



How hard is it to compute the Euler totient function?
For semiprimes, computing the Euler totient function is equivalent to factoring. Indeed, if n = pq for distinct primes p and q, then φ(n) = (p-1)(q-1) = pq - (p+q) + 1 = (n+1) - (p+q). Therefore, if you can compute φ(n), then you can compute p+q. However, it's then easy to solve for p and q because you know their sum and product (it's just a quadratic equation).


If you believe factoring is hard for semi-primes, then so is computing the Euler totient function.


*Update*! Factoring and computing the Euler totient function are known to be equivalent for arbitrary numbers, not just semiprimes. One reference is "Riemann's hypothesis and tests for primality" by Gary L. Miller. There, the equivalence is deterministic, but assumes a version of the Riemann hypothesis. See also section 10.4 of "[A computational introduction to number theory and algebra](http://shoup.net/ntb/)" by Victor Shoup for a proof of probabilistic equivalence.


