Uma maneira eficiente de calcular 𝜙 (𝜙 (p * q)) onde p e q são primos

Aug 17 2020

Deixei $p$ e $q$ ser números primos e $\phi$Função totiente de Euler. Existe uma forma eficiente de computação$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, que não é simplesmente baseado em fatoração $p-1$ e $q-1$?

Obviamente, se $p$ e $q$ não é igual a dois, $p-1$ e $q-1$ são pares e, consequentemente, sua fatoração principal é totalmente diferente da fatoração principal de $p$ e $q$. Portanto, presumo que esse atalho não exista.

Eu esqueci alguma coisa?

Respostas

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

Não, não de forma eficiente, não em geral. Suponha$p=2p'+1$ e $q=2q'+1$ Onde $p',q'$são primos. Então fatorar$pq$acredita-se que seja difícil. (Na verdade, esses primos são conhecidos como primos seguros , e acredita-se que fatorar um produto de dois primos seguros é difícil.) No entanto, temos

$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$

Se você pudesse calcular $\varphi(\varphi(pq))$ de $pq$ eficientemente para $p,q$ desta forma, então você pode fatorar $pq$ eficientemente para $p,q$deste formulário. A redução funciona da seguinte maneira. Considere a função quadrática$f$ dado por

$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$

Podemos calcular os coeficientes de $f$, Como

$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$ $$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$

então você pode usar a fórmula quadrática para resolver as raízes de $f$ e recuperar $p',q'$. A partir disso, a fatoração de$pq$ pode ser recuperado.

Então, não, você não está negligenciando nada. Provavelmente não existe uma maneira eficiente de calcular$\varphi(\varphi(pq))$ para números arbitrários $pq$ (a menos que a fatoração seja fácil).