¿Es difícil calcular la función totiente de Euler?

Question

¿Existen algoritmos eficientes para calcular el Función totiente de Euler ? (Es fácil si sabes factorizar, pero factorizar es difícil).

¿Es tan difícil de calcular como factorizar?

EDITAR : Ya que la pregunta fue contestada completamente abajo, voy a añadir una pregunta relacionada. ¿Es difícil calcular el número de factores primos de un número entero dado? No puede ser tan difícil como factorizar, puesto que ya se conoce este valor para los semiprimes, y esta información no parece ayudar en absoluto. Además, determinar si el número de factores primos es 1 o mayor que 1 se puede hacer eficientemente usando Pruebas de Primalidad.

Answer 1

Para los semiprimas, calcular la función totiente de Euler es equivalente a factorizar. En efecto, si n = pq para distintos primos p y q, entonces φ(n) = (p-1)(q-1) = pq - (p+q) + 1 = (n+1) - (p+q). Por lo tanto, si se puede calcular φ(n), entonces se puede calcular p+q. Sin embargo, luego es fácil resolver p y q porque conoces su suma y su producto (es sólo una ecuación cuadrática).

Si crees que factorizar es difícil para semiprimes, entonces también lo es calcular la función totiente de Euler.

Actualización ¡! Se sabe que la factorización y el cálculo de la función totiente de Euler son equivalentes para números arbitrarios, no sólo semiprimas. Una referencia es "Riemann's hypothesis and tests for primality" de Gary L. Miller. Allí, la equivalencia es determinista, pero asume una versión de la hipótesis de Riemann. Véase también la sección 10.4 de " Introducción computacional a la teoría de números y al álgebra "de Victor Shoup para una prueba de equivalencia probabilística.