I recently answered this related question about the Carmichael function on math.SE. The algorithm uses an unconditional lower bound so it should work just as well for the totient function because $\lambda(x) \le \phi(x)$. My answer (the only one) has not been accepted and the question has a bounty which expires tomorrow. I should not like to receive a bounty by default for an incorrect answer, so I am posting this here now as an invitation for you to correct me on math.SE. It is not an efficient algorithm as this MO question demands, but I proffer it because no algorithm has yet been given to answer it.
Also related is Carmichael's totient function conjecture which is that there are no unique solutions to this equation.

