P ve q'nun asal olduğu 𝜙 ((p * q)) 'yu hesaplamanın etkili bir yolu

Question

İzin Vermek $p$ ve $q$ asal sayılar ve $\phi$Euler'in totient işlevi. Hesaplamanın verimli bir yolu var mı$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, bu sadece faktoring temelli değildir $p-1$ ve $q-1$?

Açıkçası, eğer $p$ ve $q$ ikiye eşit değil $p-1$ ve $q-1$ eşittir ve sonuç olarak asal çarpanlara ayırma, asal çarpanlara ayırmadan tamamen farklıdır. $p$ ve $q$. Bu nedenle, böyle bir kısayol olmadığını varsayıyorum.

Bir şeyi gözden kaçırıyor muyum?

Answer 1

Hayır, verimli değil, genel olarak değil. Varsayalım$p=2p'+1$ ve $q=2q'+1$ nerede $p',q'$asal. Sonra faktoring$pq$zor olduğuna inanılıyor. (Aslında, bu astarlar güvenli astarlar olarak bilinir ve iki güvenli astarın bir ürününü faktoring yapmanın zor olduğuna inanılmaktadır.)

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

Eğer hesaplayabilirsen $\varphi(\varphi(pq))$ itibaren $pq$ verimli bir şekilde $p,q$ bu biçimin $pq$ verimli bir şekilde $p,q$bu formun. İndirgeme aşağıdaki gibi çalışır. İkinci dereceden işlevi düşünün$f$ veren

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

Katsayılarını hesaplayabiliriz $f$, gibi

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

böylece ikinci dereceden formülü kullanarak köklerini çözebilirsiniz. $f$ ve kurtar $p',q'$. Bundan çarpanlara ayırma$pq$ kurtarılabilir.

Yani hayır, hiçbir şeyi gözden kaçırmıyorsun. Hesaplamanın etkili bir yolu muhtemelen yoktur$\varphi(\varphi(pq))$ rastgele sayılar için $pq$ (faktoring kolay olmadığı sürece).