Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Complexity of inverting the Euler function
HTML articles powered by AMS MathViewer

by Scott Contini, Ernie Croot and Igor E. Shparlinski PDF
Math. Comp. 75 (2006), 983-996 Request permission

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
Similar Articles
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
  • MR Author ID: 192194
  • Email: igor@ics.mq.edu.au
  • Received by editor(s): December 6, 2004
  • Received by editor(s) in revised form: April 26, 2005
  • Published electronically: January 23, 2006
  • © Copyright 2006 American Mathematical Society
  • Journal: Math. Comp. 75 (2006), 983-996
  • MSC (2000): Primary 11A51, 11Y16, 68Q17, 68Q25
  • DOI: https://doi.org/10.1090/S0025-5718-06-01826-6
  • MathSciNet review: 2197003