Complexity of inverting the Euler function

Scott Contini*, Ernie Croot, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticle

5 Citations (Scopus)
27 Downloads (Pure)

Abstract

Given an integer n, how hard is it to find the set of all integers m such that φ(m) = n, where φ 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 φ(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 φ(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.

Original languageEnglish
Pages (from-to)983-996
Number of pages14
JournalMathematics of Computation
Volume75
Issue number254
DOIs
Publication statusPublished - Apr 2006

Bibliographical note

Copyright 2006 American Mathematical Society. First published in Mathematics of computation, Volume 75, Issue 254, published by the American Mathematical Society. The original article can be found at http://dx.doi.org/10.1090/S0025-5718-06-01826-6.

Fingerprint Dive into the research topics of 'Complexity of inverting the Euler function'. Together they form a unique fingerprint.

Cite this