Un moyen efficace de calculer 𝜙 (𝜙 (p * q)) où p et q sont premiers
Laisser $p$ et $q$ être des nombres premiers et $\phi$Fonction totient d'Euler. Existe-t-il une méthode de calcul efficace$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, ce n'est pas simplement basé sur l'affacturage $p-1$ et $q-1$?
Évidemment, si $p$ et $q$ ne valent pas deux, $p-1$ et $q-1$ sont pairs et par conséquent leur factorisation première est entièrement différente de la factorisation première de $p$ et $q$. Par conséquent, je suppose qu'aucun raccourci de ce type n'existe.
Dois-je oublier quelque chose?
Réponses
Non, pas efficacement, pas en général. Supposer$p=2p'+1$ et $q=2q'+1$ où $p',q'$sont de premier ordre. Puis affacturage$pq$est considéré comme difficile. (En effet, ces nombres premiers sont appelés nombres premiers sûrs , et la factorisation d'un produit de deux nombres premiers sûrs est considérée comme difficile.)
$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$
Si vous pouviez calculer $\varphi(\varphi(pq))$ de $pq$ efficacement pour $p,q$ de cette forme, alors vous pourriez factoriser $pq$ efficacement pour $p,q$de cette forme. La réduction fonctionne comme suit. Considérons la fonction quadratique$f$ donné par
$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$
On peut calculer les coefficients de $f$, comme
$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$ $$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$
vous pouvez donc utiliser la formule quadratique pour résoudre les racines de $f$ et récupérer $p',q'$. À partir de là, la factorisation de$pq$ peuvent être récupérés.
Donc, non, vous ne négligez rien. Il n'y a probablement aucun moyen efficace de calculer$\varphi(\varphi(pq))$ pour des nombres arbitraires $pq$ (sauf si l'affacturage est facile).