오일러 정리(Euler's Theorem)는 페르마의 소정리(Fermat's Little Theorem)를 일반화한 정리로, 양의 정수를 법(modulus)으로 하는 정수의 거듭제곱을 다룹니다. 이 정리는 초등 정수론 전반에서 폭넓게 응용되며, 특히 현대 암호학의 핵심인 RSA 암호 시스템의 이론적 기반을 제공합니다.
오일러 정리의 정의
오일러 정리는 서로소(relatively prime) 관계에 있는 임의의 두 정수 a와 n에 대해 다음 식이 항상 성립한다고 말합니다.
aφ(n) ≡ 1 (mod n)
여기서 φ(n)은 오일러 피 함수(Euler's Totient Function)로, n보다 작으면서 n과 서로소인 양의 정수의 개수를 세는 함수입니다.
증명의 핵심 아이디어
n보다 작으면서 n과 서로소인 정수들의 집합을 다음과 같이 정의합니다.
R = {x1, x2, …, xφ(n)}
집합 R의 각 원소 xi는 n보다 작은 고유한 양의 정수이며, gcd(xi, n) = 1을 만족합니다. 이제 각 원소에 a를 곱한 뒤 n으로 나눈 나머지를 구해 새로운 집합 S를 만듭니다.
S = {(ax1 mod n), (ax2 mod n), …, (axφ(n) mod n)}
a가 n과 서로소이고 xi 역시 n과 서로소이므로, 그 곱인 axi도 반드시 n과 서로소입니다. 따라서 집합 S의 모든 원소는 n보다 작으면서 n과 서로소인 정수입니다.
또한 집합 S에는 중복된 원소가 존재하지 않습니다. 만약 axi mod n = axj mod n이라면, 양변에 a의 역원을 곱해 xi = xj임을 알 수 있기 때문입니다.
따라서 두 집합 R과 S는 동일한 원소들을 담고 있으므로, 각 집합의 모든 원소를 곱한 값은 다음과 같이 서로 같습니다.
∏i=1φ(n) (axi mod n) = ∏i=1φ(n) xi
이를 정리하면 aφ(n) · (∏ xi) ≡ ∏ xi (mod n)이 되고, ∏ xi는 n과 서로소이므로 양변에서 약분할 수 있습니다. 최종적으로 다음 결론을 얻습니다.
aφ(n) ≡ 1 (mod n)
오일러 피 함수(Euler Totient Function)란?
오일러 피 함수는 주어진 정수 n 이하의 양의 정수 중에서 n과 서로소인 수의 개수를 세는 곱셈적 함수(multiplicative function)입니다. 오일러 파이 함수(phi function)라고도 부르며, 기호 ϕ로 표기합니다.
이 함수는 암호학에서 매우 중요한 역할을 합니다. n보다 작으면서 n과 서로소인 정수들의 집합은 Zn*로 표기되며, φ(n)은 바로 이 집합의 크기를 의미합니다.
오일러 피 함수의 활용 분야
- RSA 암호 시스템: 공개키와 개인키를 생성하는 과정에서 φ(n)이 핵심적으로 사용되며, 정보 보안을 위한 암호화에 필수적입니다.
- 소수 이론: 소수의 분포와 성질을 다루는 정수론 연구의 기초 도구로 활용됩니다.
- 대규모 계산과 대수 연산: 모듈러 지수 연산 등 복잡한 계산을 효율적으로 처리하는 데 도움을 줍니다.
다만 오일러 피 함수는 실무적 적용보다는 이론적 용도가 더 많으며, 직접적인 실용적 요구는 상대적으로 제한적입니다. 함수의 성질은 추상적인 설명보다 구체적인 예제를 통해 더 명확하게 이해할 수 있습니다.
오일러 피 함수의 계산 규칙
φ(n)은 다음 네 가지 기본 규칙을 이용해 Zn*의 원소 개수를 계산합니다.
- φ(1) = 0
- P가 소수(prime)이면 φ(P) = P − 1
- m과 n이 서로소이면 φ(m × n) = φ(m) × φ(n)
- P가 소수이면 φ(Pe) = Pe − Pe−1
이 네 가지 규칙을 조합하면 임의의 n에 대한 φ(n) 값을 구할 수 있습니다. 먼저 n을 소인수분해합니다.
n = P1e1 × P2e2 × ⋯ × Pkek
그러면 φ(n)은 다음과 같이 계산됩니다.
φ(n) = (P1e1 − P1e1−1) × (P2e2 − P2e2−1) × ⋯ × (Pkek − Pkek−1)
암호학적 의의
φ(n)을 구하는 난이도는 n을 소인수분해하는 난이도에 직결됩니다. n이 충분히 큰 두 소수의 곱일 경우, n 자체는 공개하더라도 φ(n)을 계산하는 것이 사실상 불가능합니다. 바로 이 비대칭성이 RSA 암호 시스템의 안전성을 뒷받침하는 핵심 원리입니다.