Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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?)


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
Email: scontini@ics.mq.edu.au

Ernie Croot
Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332
Email: ecroot@math.gatech.edu

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
Email: igor@ics.mq.edu.au

DOI: http://dx.doi.org/10.1090/S0025-5718-06-01826-6
PII: S 0025-5718(06)01826-6
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