[%] Euler totient φ 빠르게 계산하는 법 알려주라

[익명(118.40)]

정의 그대로는 너무 느림

[ns(qwer2357)]

만약에 그런게 있다고 생각해봐. 그럼 n=pq를 넣으면 pq-p-q+1을 뱉으니 p+q값을 알지? 그럼 2차방정식 근의공식으로 p,q가 구해져. 뭔말이냐면 그게 되면 암호가 다깨짐.. factorization 안거치곤 불가능하다