Complexity of inverting the Euler function

DOI10.1090/S0025-5718-06-01826-6zbMath1158.11003arXivmath/0404116MaRDI QIDQ3377006

Ernie Croot, Scott Contini, 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) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Factorization; primality (11A51) Primality (11Y11)

Related Items (2)

Primitive finite nilpotent linear groups over number fields ⋮ Diophantine equations involving Euler’s totient function

Cites Work

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

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