Complexity of Inverting the Euler Function

Abstract

We present an algorithm to invert the Euler function $\varphi (m)$. The algorithm, for a given $n\ge 1$, in polynomial time ``on average'', finds the set $\Psi (n)$ of all solutions $m$ to $\varphi (m)=n$. In fact, in the worst case, $\Psi (n)$ is exponentially large, and cannot be computed in polynomial time. In the opposite direction, we show, under a widely accepted number theoretic conjecture, that there is a polynomial time reduction of the Partition Problem, an NP-complete problem, to the problem of deciding whether $\varphi (m)=n$ has a solution for a small set of integers n. This shows that the problem of deciding whether a given finite set of integers S contains a totient is NP-complete. A totient is an integer n that lies in the image of the phi function; that is, an integer n for which there exists an integer m solving phi(m) = n. Finally, we establish close links between of inverting the Euler function and the integer factorization problem.

Slight restatement of results in introduction and in section 4