Are there any efficient algorithms for computing the Euler 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.