오일러 파이 함수 계산기

1부터 n까지의 수 중 n과 서로소인 것의 개수입니다. φ(12) = 4인데, 12와 서로소인 수가 1, 5, 7, 11 넷이기 때문입니다. 계산은 φ(n) = n × ∏(1 − 1/p)로 하며, p는 n의 서로 다른 소인수입니다.

반영하지 않습니다. 서로 다른 소인수마다 (1 − 1/p)를 한 번씩만 곱합니다. 12 = 2²·3이지만 (1 − 1/2)를 두 번 곱하지 않고 한 번만 곱해 12 × 1/2 × 2/3 = 4가 됩니다. 지수를 곱하면 답이 절반으로 틀어지는 흔한 실수입니다. 다만 n 자체에는 지수가 들어 있으므로, φ(pᵏ) = pᵏ − pᵏ⁻¹처럼 결과에는 지수가 반영됩니다.

RSA의 안전성이 φ(n)을 구할 수 없다는 데 기대고 있습니다. 서로 다른 소수 p, q로 n = pq를 만들면 φ(n) = (p−1)(q−1)입니다. 공개키에는 n만 실리는데, 개인키를 만들려면 φ(n)이 필요하고 φ(n)을 알려면 p와 q를 알아야 합니다. 즉 큰 수를 소인수분해하기 어렵다는 것이 RSA의 안전성 전부입니다. 반대로 n을 인수분해할 수 있으면 φ(n)이 나오고 개인키도 만들 수 있습니다.

gcd(a, n) = 1이면 a^φ(n) ≡ 1 (mod n)이라는 정리입니다. 지수를 φ(n)으로 나눈 나머지만 보면 되므로 어마어마한 거듭제곱의 나머지를 바로 구할 수 있습니다. n이 소수일 때의 특수한 경우가 페르마의 소정리 a^(p−1) ≡ 1 (mod p)입니다. 다만 서로소가 아니면 성립하지 않아서, 2^4 mod 10은 1이 아니라 6입니다.

1, 2, 4, 홀수 소수의 거듭제곱 pᵏ, 그리고 그 두 배인 2pᵏ에만 있습니다. 8, 12, 15, 16, 20처럼 흔한 수에는 없습니다. 원시근이란 거듭제곱만으로 n과 서로소인 수를 전부 만들어 내는 수를 말하며, 있을 때 그 개수는 정확히 φ(φ(n))개입니다. 디피-헬만 키 교환이 이런 생성원을 쓰고, 그래서 소수 p를 골라 씁니다.

약수들의 φ를 모두 더하면 n이 됩니다. 12의 약수 1, 2, 3, 4, 6, 12의 φ는 1, 1, 2, 2, 2, 4이고 더하면 12입니다. 또 서로소인 두 수 m, k에 대해 φ(mk) = φ(m)φ(k)가 성립합니다. 다만 서로소가 아니면 성립하지 않아서, φ(4)φ(6)는 4인데 φ(24)는 8입니다. 소수 p에서는 φ(p) = p − 1이라 φ(n)/n이 1에 가까울수록 소수에 가깝습니다.