Complexity of Inverting the Euler Function
| dc.creator | Contini, Scott | |
| dc.creator | Croot, Ernie | |
| dc.creator | Shparlinski, Igor | |
| dc.date | 2004-04-06 | |
| dc.date | 2004-04-23 | |
| dc.date.accessioned | 2026-07-07T05:07:11Z | |
| dc.date.available | 2026-07-07T05:07:11Z | |
| dc.description | We present an algorithm to invert the Euler function $ϕ(m)$. The algorithm, for a given $n \geq 1$, in polynomial time ``on average'', finds the set $Ψ(n)$ of all solutions $m$ to $ϕ(m) = n$. In fact, in the worst case, $Ψ(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 $ϕ(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. | |
| dc.description | Slight restatement of results in introduction and in section 4 | |
| dc.identifier | https://arxiv.org/abs/math/0404116 | |
| dc.identifier | http://arxiv.org/abs/math/0404116 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70761 | |
| dc.subject | Number Theory | |
| dc.subject | 11Y16 | |
| dc.title | Complexity of Inverting the Euler Function | |
| dc.type | text |