Complexity of inverting the Euler function

DOI10.1090/S0025-5718-06-01826-6MaRDI QIDQ3377006zbMATH OpenFDO

Authors Scott Contini, Ernie Croot, Igor E. Shparlinski

Publication date 27 March 2006

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0404116

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Number-theoretic algorithms; complexity (11Y16) Factorization; primality (11A51) Primality (11Y11)

Abstract: We present an algorithm to invert the Euler function $phi(m)$. The algorithm, for a given $ngeq1$, in polynomial time ``on average, finds the set $Psi(n)$ of all solutions $m$ to $phi(m)=n$. In fact, in the worst case, $Psi(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 $phi(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.

Recommendations

• On the arithmetic complexity of Euler function
• Rigorous Time/Space Trade-offs for Inverting Functions
• Structural analysis of the complexity of inverse functions
• Euler's totient function and its inverse
• On the Inverse of Erlang's Function
• Lower bounds on the time/memory tradeoff of function inversion
• Computational complexity of functions
• Computing Inverse ST in Linear Complexity
• On the complexity of inverting integer and polynomial matrices

Cites work

• scientific article; zbMATH DE number 2154269 (Why is no real title available?)
• scientific article; zbMATH DE number 4118426 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• scientific article; zbMATH DE number 4185749 (Why is no real title available?)
• A hyperelliptic smoothness test. I
• Euler's function in residue classes
• Factoring integers with elliptic curves
• On the normal number of prime factors of \(\phi(n)\)
• PRIMES is in P
• Popular values of Euler's function
• Residue classes free of values of Euler's function
• Riemann's hypothesis and tests for primality
• Shifted primes without large prime factors
• Some computational experiments in number theory
• The Equation Φ(x) = k
• The distribution of values of the Euler function
• The number of solutions of \(\varphi (x)=m\)
• There are infinitely many Carmichael numbers
• Values of the Euler function in various sequences

Cited in

(5)

• Diophantine equations involving Euler's totient function
• Computing Inverse ST in Linear Complexity
• Primitive finite nilpotent linear groups over number fields
• Computing the inverses, their power sums, and extrema for Euler's totient and other multiplicative functions
• On the arithmetic complexity of Euler function

This page was built for publication: Complexity of inverting the Euler function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3377006)