Complexity of Inverting the Euler Function

Scott Contini, Ernie Croot, Igor Shparlinski

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…