ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > INTEGER FACTORISATION:
Reports tagged with Integer factorisation:
TR04-035 | 10th April 2004
Scott Contini, Ernie Croot, Igor E. Shparlinski

Complexity of Inverting the Euler Function

We 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 ... more >>>




ISSN 1433-8092 | Imprint