Complexity of Inverting the Euler Function

Details Complexity of Inverting the Euler Function Complexity of Inverting the Euler Function

2004-04-06

arxiv.org/abs/math/0404116v3

Mathematics

Number Theory

Slight restatement of results in introduction and in section 4

Scientific paper

We present an algorithm to invert the Euler function $\phi(m)$. The algorithm, for a given $n \geq 1$, in polynomial time ``on average'', finds the set $\Psi(n)$ of all solutions $m$ to $\phi(m) = n$. In fact, in the worst case, $\Psi(n)$ is exponentially large, and cannot be computed in polynomial time. In the opposite direction, we show, under a widely accepted number theoretic conjecture, that there is a polynomial time reduction of the Partition Problem, an NP-complete problem, to the problem of deciding whether $\phi(m) = n$ has a solution for a small set of integers n. This shows that the problem of deciding whether a given finite set of integers S contains a totient is NP-complete. A totient is an integer n that lies in the image of the phi function; that is, an integer n for which there exists an integer m solving phi(m) = n. Finally, we establish close links between of inverting the Euler function and the integer factorization problem.

Affiliated with

Also associated with

No associations

Rating

Complexity of Inverting the Euler Function does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity of Inverting the Euler Function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Inverting the Euler Function will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-601382