¿Lo difícil es calcular la función φ de Euler?

Question

Existen algoritmos eficientes para el cálculo de la de Euler totient función? (Es fácil si usted puede factor, pero el factoring es duro.)

Es el caso de que este cálculo es tan duro como el factoring?

EDIT: Ya que la pregunta fue respondido completamente a continuación, voy a añadir una pregunta relacionada. ¿Qué tan difícil es calcular el número de factores primos de un entero dado? Esto no puede ser tan duro como el factoring, puesto que usted ya conoce este valor para la semi-primes, y esta información no parece ayudar en todo. También, la determinación de si el número de factores primos es 1 o mayor que 1 se puede hacer de manera eficiente el uso de Pruebas de Primalidad.

Answer 1

Para semiprimes, el cálculo de Euler totient función es equivalente a la factorización. En efecto, si n = pq para distintos números primos p y q, entonces φ(n) = (p-1)(q-1) = pq - (p+q) + 1 = (n+1) - (p+q). Por lo tanto, si usted puede calcular φ(n), entonces se puede calcular p+q. Sin embargo, es fácil de resolver para p y q, porque usted sabe que su suma y el producto (es sólo una ecuación de segundo grado).

Si usted cree que el factoring es duro para la semi-números primos, entonces también lo es la computación de Euler totient función.

Actualización! El Factoring y la computación de Euler totient función son conocidos por ser equivalente arbitrarias de números, no sólo semiprimes. Una referencia es "la hipótesis de Riemann y pruebas de primalidad" por Gary L. Miller. Allí, la equivalencia es determinista, sino que asume una versión de la hipótesis de Riemann. Véase también la sección 10.4 de "Un computacional introducción a la teoría de números y álgebra" por Victor Shoup para una prueba probabilístico de equivalencia.