TY - JOUR

T1 - Complexity of inverting the Euler function

AU - Contini, Scott

AU - Croot, Ernie

AU - Shparlinski, Igor E.

N1 - 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.

PY - 2006/4

Y1 - 2006/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33646422755&partnerID=8YFLogxK

U2 - 10.1090/S0025-5718-06-01826-6

DO - 10.1090/S0025-5718-06-01826-6

M3 - Article

VL - 75

SP - 983

EP - 996

JO - Mathematics of Computation

JF - Mathematics of Computation

SN - 0025-5718

IS - 254

ER -