Igor Shparlinski
Macquarie
Title:
Inverting the Euler Function (joint work with Scott Contini and Ernie Croot)
We present an algorithm to invert the Euler function $\varphi(m)$.
The algorithm, given the prime number factorization of an
integer $n\ge 1$, in polynomial time ``on average'',
finds the set $\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 Partition Problem
can be reduced, in polynomial time, to the problem of deciding whether
$\varphi(m) = n$ has a solution, for polynomially many values of $n$.
Finally, we establish close links between the problem of inverting
the Euler function and the integer factorization problem.