Una forma eficiente de calcular 𝜙 (𝜙 (p * q)) donde pyq son primos
Dejar $p$ y $q$ ser números primos y $\phi$Función totient de Euler. ¿Existe una forma eficiente de computar$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, que no se basa simplemente en factorizar $p-1$ y $q-1$?
Obviamente, si $p$ y $q$ no es igual a dos, $p-1$ y $q-1$ son pares y, en consecuencia, su factorización prima es completamente diferente de la factorización prima de $p$ y $q$. Por lo tanto, asumo que no existe tal atajo.
¿Me olvido de algo?
Respuestas
No, no de manera eficiente, no en general. Suponer$p=2p'+1$ y $q=2q'+1$ dónde $p',q'$son primos. Entonces factorizando$pq$se cree que es difícil. (De hecho, estos primos se conocen como primos seguros y se cree que es difícil factorizar un producto de dos primos seguros).
$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$
Si pudieras calcular $\varphi(\varphi(pq))$ desde $pq$ eficientemente para $p,q$ de esta forma, entonces podría factorizar $pq$ eficientemente para $p,q$de esta forma. La reducción funciona de la siguiente manera. Considere la función cuadrática$f$ dada por
$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$
Podemos calcular los coeficientes de $f$, como
$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$ $$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$
entonces puedes usar la fórmula cuadrática para resolver las raíces de $f$ y recuperar $p',q'$. De esto la factorización de$pq$ se puede recuperar.
Entonces, no, no está pasando por alto nada. Es probable que no exista una forma eficiente de calcular$\varphi(\varphi(pq))$ para números arbitrarios $pq$ (a menos que factoraje sea fácil).