ECCC-Report TR04-035https://eccc.weizmann.ac.il/report/2004/035Comments and Revisions published for TR04-035en-usWed, 14 Apr 2004 17:32:57 +0300
Paper TR04-035
| Complexity of Inverting the Euler Function |
Scott Contini,
Ernie Croot,
Igor E. Shparlinski
https://eccc.weizmann.ac.il/report/2004/035We present an algorithm to invert the Euler function $\varphi(m)$. The algorithm, for a given integer $n\ge 1$, in polynomial time ``on average'', finds theset $\Psi(n)$ of all solutions $m$ to the equation $\varphi(m) =n$. In fact, in the worst case the set $\Psi(n)$ is exponentially large and cannot be constructed by a polynomial time algorithm. In the opposite direction, we show, under some widely accepted number theoretic conjecture, that the problem of deciding whether $\varphi(m) =n$ for some $m$ is {\bf NP}-complete. Finally, we establish close links between the problem of inverting the Euler function and the integer factorisation problem.
Wed, 14 Apr 2004 17:32:57 +0300https://eccc.weizmann.ac.il/report/2004/035