Un moyen efficace de calculer 𝜙 (𝜙 (p * q)) où p et q sont premiers

Aug 17 2020

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

2 D.W. Aug 18 2020 at 00:35

Non, pas efficacement, pas en général. Supposer$p=2p'+1$ et $q=2q'+1$$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).