Un modo efficiente per calcolare 𝜙 (𝜙 (p * q)) dove p e q sono primi
Permettere $p$ e $q$ essere numeri primi e $\phi$Funzione totiente di Eulero. Esiste un modo efficiente di calcolare$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, che non si basa semplicemente sul factoring $p-1$ e $q-1$?
Ovviamente, se $p$ e $q$ non è uguale a due, $p-1$ e $q-1$ sono pari e di conseguenza la loro scomposizione in fattori primi è completamente diversa dalla scomposizione in fattori primi di $p$ e $q$. Pertanto presumo che non esista tale scorciatoia.
Trascuro qualcosa?
Risposte
No, non in modo efficiente, non in generale. Supponiamo$p=2p'+1$ e $q=2q'+1$ dove $p',q'$sono prime. Quindi factoring$pq$si crede che sia difficile. (In effetti, questi numeri primi sono noti come numeri primi sicuri e si ritiene che la scomposizione in fattori di un prodotto di due numeri primi sicuri sia difficile).
$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$
Se potessi calcolare $\varphi(\varphi(pq))$ a partire dal $pq$ in modo efficiente per $p,q$ di questa forma, quindi potresti fattorizzare $pq$ in modo efficiente per $p,q$di questa forma. La riduzione funziona come segue. Considera la funzione quadratica$f$ dato da
$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$
Possiamo calcolare i coefficienti di $f$, come
$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$ $$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$
quindi puoi usare la formula quadratica per risolvere le radici di $f$ e recuperare $p',q'$. Da questo la fattorizzazione di$pq$ può essere recuperato.
Quindi no, non stai trascurando nulla. Probabilmente non esiste un modo efficiente per eseguire il calcolo$\varphi(\varphi(pq))$ per numeri arbitrari $pq$ (a meno che il factoring non sia facile).