오일러 피 함수는 암호학의 RSA 암호학에서 핵심적으로 사용된다고 한다.
수론에서 오일러 피 함수(-函數, 영어: Euler’s phi (totient) function)는 정수환의 몫환의 가역원을 세는 함수이다. 즉, n이 양의 정수일 때, ϕ(n)은 n과 서로소인 1부터 n까지의 정수의 개수와 같다. 예를 들어, 1부터 6까지의 정수 가운데 1, 5 둘만 6과 서로소이므로, ϕ(6) = 2이다. 1부터 10까지의 정수는 모두 11과 서로소이며, 11은 자기 자신과 서로소가 아니므로, ϕ(11) = 10이다. 1은 자기 자신과 서로소이므로, ϕ(1) = 1이다. - https://ko.wikipedia.org/wiki/오일러_피_함수 참고
이용할 수 있는 것은 아래와 같다.
오일러 피 함수는 ‘서로소인 두 수의 곱셈을 보존하는 보존적 함수’인 곱셈적 함수이다. 따라서 아래가 성립한다.
$\phi(mn)=\phi(m)\phi(n)$
소인수를 통해 다음과 같이 구할 수 있다. 오일러 곱 공식(Euler product formula)이라 한다.
$\phi(n)=n{\prod\over p|n}(1-{1\over p})$
ex)
$\phi(20) = 20(1 - {1 \over 2})(1 - {1 \over 5}) = 20 * {1 \over 2} * {4 \over 5} = 8$
특히 소수 $p$의 경우 아래가 성립한다.
$\phi(p) = p - 1$
3번 정의는 자명하지만 2번 식을 적용하는 것으로도 결과는 같다.
$N$을 소인수분해하면 $p_ap_bp_c...$로 나타낼 수 있다. 여기서 특이한 점은 소인수를 구하기 위해 $N$의 제곱근까지 탐색할 때, 제곱근보다 큰 $p$ 중 가장 큰 수는 0개 또는 1개이다. 왜냐하면, 만약 제곱근보다 큰 소수가 2개 이상일 경우, 이 중 2개의 소수만 곱하더라도 $N$을 초과하기 때문에 모순된다.
최적화된 풀이를 보니, isPrime 검증이 필요 없이 pivot까지 i로 나눴을 때 만약 모두 나눈 수가 1이 아니라면 그 수는 소수이고 pivot보다 큰 수 1개 뿐이게 된다. (만약 pivot보다 큰 소수 2개가 남는다면 그 2개 수의 곱이 N을 초과하기 때문에 불가능하다.) 따라서 2 다 나누고 3 다 나누고 5 다 나누고 … 마지막에 남는 수가 1보다 크면 $1-{1 \over N}$을 한번 더 계산해주면 된다!!
또한 소수 판정은 2의 배수는 계산이 필요 없으므로, 2에 대해서만 따로 계산하면 전체 시간을 반으로 줄이는 최적화를 할 수 있다.
오일러 피를 이용해 N으로 도착하는 서로소의 개수가 간선의 개수와 같다. 이를 2~N번 반복한다.