Complexity of inverting the Euler function

Given an integer n, how hard is it to find the set of all integers m such that phi(m) = n, where phi is the Euler totient function? We present a certain basic algorithm which, given the prime number factorization of n, in polynomial time "on average" (that is, (log n) (O(1))), finds the set of all such solutions m. In fact, in the worst case this set of solutions is exponential in log n, and so cannot be constructed by a polynomial time algorithm. In the opposite direction, we show, under a widely accepted number theoretic conjecture, that the Partition Problem, an NP-complete problem, can be reduced in polynomial ( in the input size) time to the problem of deciding whether phi(m) = n has a solution, for polynomially ( in the input size of the Partition Problem) many values of n ( where the prime factorizations of these n are given). What this means is that the problem of deciding whether there even exists a solution m to phi(m) = n, let alone finding any or all such solutions, is very likely to be intractable. Finally, we establish close links between the problem of inverting the Euler function and the integer factorization problem.