24
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ @Rune, I'd suggest you just ask a new question in this case. It's easier for everyone. $\endgroup$
    – Scott Morrison
    Oct 29, 2009 at 19:42
  • $\begingroup$ 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). $\endgroup$
    – Juan Bermejo Vega
    Mar 22, 2013 at 14:01
  • $\begingroup$ Correction, I am not editting the post: I forgot I do not have enough rights in MO. Maybe someone else can do it. $\endgroup$
    – Juan Bermejo Vega
    Mar 22, 2013 at 14:03

1 Answer 1

Reset to default
39
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ And factoring being hard for semi-primes is the whole point of the RSA algorithm. $\endgroup$
    – Qiaochu Yuan
    Oct 29, 2009 at 15:50
  • 3
    $\begingroup$ 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. $\endgroup$
    – aorq
    Oct 29, 2009 at 16:00
  • $\begingroup$ Thanks! That answers the question completely. Another question: How hard is it to compute the number of prime factors of a given integer? $\endgroup$
    – Rune
    Oct 29, 2009 at 17:13
  • 4
    $\begingroup$ @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). $\endgroup$
    – aorq
    Oct 29, 2009 at 17:43
  • $\begingroup$ @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). $\endgroup$
    – Rune
    Oct 30, 2009 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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