Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Complexity of inverting the Euler function

Authors: Scott Contini, Ernie Croot and Igor E. Shparlinski
Journal: Math. Comp. 75 (2006), 983-996
MSC (2000): Primary 11A51, 11Y16, 68Q17, 68Q25
Published electronically: January 23, 2006
MathSciNet review: 2197003
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given an integer $ n$, how hard is it to find the set of all integers $ m$ such that $ \varphi(m) = n$, where $ \varphi$ is the Euler totient function? We present a certain basic algorithm which, given the prime number factorization of $ n$, in polynomial time ``on average'' (that is, $ (\log n)^{O(1)}$), finds the set of all such solutions $ m$. In fact, in the worst case this set of solutions is exponential in $ \log n$, and so cannot be constructed by a polynomial time algorithm. In the opposite direction, we show, under a widely accepted number theoretic conjecture, that the PARTITION PROBLEM, an NP-complete problem, can be reduced in polynomial (in the input size) time to the problem of deciding whether $ \varphi(m) = n$ has a solution, for polynomially (in the input size of the PARTITION PROBLEM) many values of $ n$ (where the prime factorizations of these $ n$ are given). What this means is that the problem of deciding whether there even exists a solution $ m$ to $ \varphi(m) = n$, let alone finding any or all such solutions, is very likely to be intractable. Finally, we establish close links between the problem of inverting the Euler function and the integer factorization problem.

References [Enhancements On Off] (What's this?)

  • 1. M. Agrawal, N. Kayal and N. Saxena, `PRIMES is in P', Ann. of Math. (2) 160 (2004), 781-793. MR 2123939
  • 2. W. R. Alford, A. Granville and C. Pomerance, `There are infinitely many Carmichael numbers', Annals of Math., 140 (1994), 703-722. MR 1283874 (95k:11114)
  • 3. R. C. Baker and G. Harman, `Shifted primes without large prime factors', Acta Arith., 83 (1998), 331-361. MR 1610553 (99b:11104)
  • 4. A. Balog, `The prime $ k$-tuplets conjecture on average', Analytic Number Theory, Progress in Mathematics 85, Birkhäuser, Boston, 1990, 47-75.MR 1084173 (92e:11105)
  • 5. W. Banks, J. B. Friedlander, C. Pomerance and I. E. Shparlinski, `Multiplicative structure of values of the Euler function', High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams, Fields Institute Communications, vol. 41, Amer. Math. Soc., 2004, 29-48.MR 2075645 (2005f:11217)
  • 6. W. Banks, K. Ford, F. Luca, F. Pappalardi and I. E. Shparlinski, `Values of the Euler function in various sequences', Monatsh. Math., 146 (2005), 1-19.
  • 7. P. T. Bateman, `On the distribution of values of the Euler function', Acta Arith., 21 (1972), 329-345. MR 0302586 (46:1730)
  • 8. W. Bosma, `Some computational experiments in number theory', Preprint, 2004.
  • 9. R. Crandall and C. Pomerance, Prime numbers: A Computational perspective, Springer-Verlag, Berlin, 2001. MR 1821158 (2002a:11007)
  • 10. T. Dence and C. Pomerance, `Euler's function in residue classes', The Ramanujan J., 2 (1998), 7-20. MR 1642868 (99k:11148)
  • 11. L. E. Dickson, `A new extension of Dirichlet's theorem on prime numbers', Messenger of Mathematics, 33 (1904), 155-161.
  • 12. P. Erdos, `On the normal number of prime factors of $ p-1$ and some related problems concerning Euler's $ \phi$-function', Quart. J. Math., 6 (1935), 205-213.
  • 13. P. Erdos and C. Pomerance, `On the normal number of prime factors of $ \varphi(n)$', Rocky Mountain J. Math., 15 (1985), 343-352. MR 0823246 (87e:11112)
  • 14. K. Ford, `The number of solutions of $ \varphi(x)=m$', Annals of Math., 150 (1999), 283-311. MR 1715326 (2001e:11099)
  • 15. K. Ford, S. Konyagin and C. Pomerance, `Residue classes free of values of Euler's function', Proc. Number Theory in Progress, Walter de Gruyter, Berlin, 1999, 805-812. MR 1689545 (2000f:11120)
  • 16. H. W. Lenstra, Jr., `Factoring integers with elliptic curves' Annals of Math., 126 (1987), 649-673. MR 0916721 (89g:11125)
  • 17. H. W. Lenstra, Jr., J. Pila and C. Pomerance, `A hyperelliptic smoothness test, I', Phil. Trans. of the Royal Society of London, Ser. A., 345 (1993), 397-408. MR 1253501 (94m:11107)
  • 18. N. S. Mendelsohn, `The equation $ \varphi(x)=k$', Math. Magazine, 49 (1976), 37-39. MR 0396385 (53:252)
  • 19. G. L. Miller, `Riemann's hypothesis and tests for primality', J. Comput. System Sci., 13 (1976), 300-317. MR 0480295 (58:470a)
  • 20. L. L. Pennesi, `A method for solving $ \varphi(x)=n$', Amer. Math. Monthly, 74 (1957), 497-499.
  • 21. C. Pomerance, `Popular values of Euler's function', Mathematika, 27 (1980), 84-89. MR 0581999 (81k:10076)
  • 22. C. Pomerance, `Two methods in elementary analytic number theory', Number theory and application, R. A. Mollin, ed., Kluwer Acad. Publ., Dordrecht, 1989, 135-161. MR 1123073 (92j:11107)
  • 23. G. Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge University Press, UK, 1995. MR 1342300 (97e:11005b)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11A51, 11Y16, 68Q17, 68Q25

Retrieve articles in all journals with MSC (2000): 11A51, 11Y16, 68Q17, 68Q25

Additional Information

Scott Contini
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia

Ernie Croot
Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia

Keywords: Euler function, integer factorisation, Partition problem, NP-completeness
Received by editor(s): December 6, 2004
Received by editor(s) in revised form: April 26, 2005
Published electronically: January 23, 2006
Article copyright: © Copyright 2006 American Mathematical Society

American Mathematical Society