p와 q가 소수 인 𝜙 (𝜙 (p * q))를 계산하는 효율적인 방법
허락하다 $p$ 과 $q$ 소수이고 $\phi$오일러의 끈기 기능. 효율적인 컴퓨팅 방법이 있습니까?$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, 그것은 단순히 팩토링을 기반으로하지 않습니다. $p-1$ 과 $q-1$?
분명히 $p$ 과 $q$ 2와 같지 않다. $p-1$ 과 $q-1$ 균등하고 결과적으로 소인 수화는 소인 수화와 완전히 다릅니다. $p$ 과 $q$. 따라서 나는 그러한 지름길이 없다고 가정합니다.
내가 뭔가를 간과합니까?
답변
아니요, 일반적으로 효율적이지 않습니다. 가정$p=2p'+1$ 과 $q=2q'+1$ 어디 $p',q'$프라임입니다. 그런 다음 인수 분해$pq$어렵다고 믿어집니다. (실제로 이러한 소수를 안전 소수 라고하며 두 개의 안전 소수의 곱을 인수 분해하는 것은 어렵다고 믿어집니다.) 그러나 우리는
$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$
계산할 수 있다면 $\varphi(\varphi(pq))$ ...에서 $pq$ 효율적으로 $p,q$ 이 형태의 $pq$ 효율적으로 $p,q$이 양식의. 감소는 다음과 같이 작동합니다. 2 차 함수 고려$f$ 주어진
$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$
계수를 계산할 수 있습니다. $f$, 같이
$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$ $$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$
따라서 2 차 공식을 사용하여 $f$ 그리고 회복 $p',q'$. 이로부터 분해$pq$ 복구 할 수 있습니다.
그래서, 당신은 아무것도 간과하지 않습니다. 효율적인 계산 방법이 없을 가능성이 높습니다.$\varphi(\varphi(pq))$ 임의의 숫자 $pq$ (분해가 쉽지 않은 경우).