오일러 파이 함수 (Euler's totient function)
쉽게 풀면
숫자 10을 예로 들어봅시다. 1부터 10까지의 수 중에서 10과 최대공약수와 최소공배수가 1인, 즉 10과 아무런 공통 약수를 갖지 않는 숫자만 골라내 보면 1, 3, 7, 9로 총 4개입니다. 이 개수 4가 바로 10에 대한 오일러 파이 함수의 값이며 φ(10)=4로 씁니다. 소수 p에 대해서는 자기 자신을 제외한 1부터 p-1까지 모든 수가 p와 서로소이므로 φ(p)=p-1로 아주 간단하게 계산됩니다. 이 함수는 특히 암호학에서 매우 중요한데, 두 개의 큰 소수를 곱해 만든 합성수 n에 대한 오일러 파이 함수 값이 RSA 암호의 핵심 계산에 사용되기 때문입니다.
왜 중요한가
오일러 파이 함수는 RSA와 같은 공개키 암호 시스템의 수학적 기반을 이루기 때문에, 정보보안·암호학 논문에서 핵심적으로 다뤄집니다. 또한 정수론 내부에서는 오일러 정리(모듈러 지수 연산의 기본 성질)와 직결되어 있어, 모듈러 연산을 다루는 이론 논문에서도 자주 등장하는 기초 개념입니다.
논문에서는 이렇게 쓰입니다
이 문장은 암호 시스템을 설계할 때, 두 소수를 곱해 만든 큰 수에 대해 오일러 파이 함수 값을 구하고 이를 이용해 암호화·복호화에 쓰이는 두 개의 키를 만들어냈다는 뜻입니다. 공개키 암호 방식을 다루는 정보보안·암호학 논문에서 등장하는 대표적인 개념입니다.
정수론·이론전산학 논문에서는 큰 지수를 다룰 때 오일러 정리를 이용해 지수 계산을 단순화하는 표준 기법으로 이 함수가 인용됩니다.
조금 더 깊게 보면
오일러 파이 함수는 소인수분해를 알고 있으면 각 소인수에 대한 식을 곱해 비교적 쉽게 계산할 수 있지만, 거꾸로 n의 소인수분해를 모르는 상태에서 φ(n)만으로 원래의 소인수를 알아내는 것은 매우 어려운 문제로 여겨집니다. RSA 암호의 안전성은 바로 이 비대칭성, 즉 큰 합성수를 소인수분해하는 것이 계산적으로 어렵다는 사실에 기반합니다. 또한 이 함수는 모듈러 지수 연산에서 지수를 φ(n)을 기준으로 줄일 수 있게 해주는 오일러 정리와 함께 다뤄지는 경우가 많습니다.
주의할 점
오일러 파이 함수는 곱셈에 대해 "곱셈적(multiplicative)"이라는 성질을 가지는데, 이는 두 수가 서로소일 때에만 φ(mn)=φ(m)φ(n)이 성립한다는 뜻입니다. 서로소가 아닌 경우 이 공식을 그대로 적용하면 틀린 값이 나오므로, 계산할 때는 반드시 소인수분해를 통해 각 소인수별로 나누어 계산해야 합니다.