Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Are there any efficient algorithms for computing the Euler totient function? (It's easy if you can factor, but factoring is hard.)

Is it the case that computing this is as hard as factoring?

EDIT: Since the question was completely answered below, I'm going to add a related question. How hard is it to compute the number of prime factors of a given integer? This can't be as hard as factoring, since you already know this value for semi-primes, and this information doesn't seem to help at all. Also, determining whether the number of prime factors is 1 or greater than 1 can be done efficiently using Primality Testing.

share|improve this question
5  
@Rune, I'd suggest you just ask a new question in this case. It's easier for everyone. –  Scott Morrison Oct 29 '09 at 19:42
    
The OP finally asked his second question in another post: since it is rather independent from the original question, and since the latter has been answered, I think we can make this post more clear if remove the second question (so, I'm editting the post). –  Juan Bermejo Vega Mar 22 '13 at 14:01
    
Correction, I am not editting the post: I forgot I do not have enough rights in MO. Maybe someone else can do it. –  Juan Bermejo Vega Mar 22 '13 at 14:03
add comment

1 Answer

up vote 21 down vote accepted

For semiprimes, computing the Euler totient function is equivalent to factoring. Indeed, if n = pq for distinct primes p and q, then φ(n) = (p-1)(q-1) = pq - (p+q) + 1 = (n+1) - (p+q). Therefore, if you can compute φ(n), then you can compute p+q. However, it's then easy to solve for p and q because you know their sum and product (it's just a quadratic equation).

If you believe factoring is hard for semi-primes, then so is computing the Euler totient function.

Update! Factoring and computing the Euler totient function are known to be equivalent for arbitrary numbers, not just semiprimes. One reference is "Riemann's hypothesis and tests for primality" by Gary L. Miller. There, the equivalence is deterministic, but assumes a version of the Riemann hypothesis. See also section 10.4 of "A computational introduction to number theory and algebra" by Victor Shoup for a proof of probabilistic equivalence.

share|improve this answer
3  
And factoring being hard for semi-primes is the whole point of the RSA algorithm. –  Qiaochu Yuan Oct 29 '09 at 15:50
3  
Note also that if you can compute Euler's totient function for, say, numbers with at least three distinct prime factors, then you can do it for two distinct prime factors also by computing φ(n*p)/(p-1) for some p not dividing n. Thus, you can't sidestep the issue in some trivial way. –  aorq Oct 29 '09 at 16:00
    
Thanks! That answers the question completely. Another question: How hard is it to compute the number of prime factors of a given integer? –  Rune Oct 29 '09 at 17:13
4  
@Rune: I don't know the answer for sure, but I've thought about that question. To the best of my knowledge (and Peter Sarnak's), there's no known method of computing any function that even "correlates" (in an analytic number theoretic sense) with the Möbius function μ(n). In particular, I believe there is no fast algorithm for determining the number of prime factors (distinct or not -- doesn't really matter). –  aorq Oct 29 '09 at 17:43
    
@A. Rex: Thanks! It would be interesting if there were a way to show that this is as hard as factoring (or some such statement). –  Rune Oct 30 '09 at 17:55
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.