Complexity of inverting the Euler function

DOI10.1090/S0025-5718-06-01826-6zbMATH Open1158.11003arXivmath/0404116MaRDI QIDQ3377006FDOQ3377006

Authors: Scott Contini, Ernie Croot, Igor E. Shparlinski 

Publication date: 27 March 2006

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Diophantine equations involving Euler’s totient function
• On the arithmetic complexity of Euler function
• Computing Inverse ST in Linear Complexity
• Primitive finite nilpotent linear groups over number fields

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)