오일러의 정리(Euler’s theorem)는 수학과 과학 여러 분야에서 쓰이지만, 여기서는 정수론에서의 오일러의 정리를 다루겠습니다. 이 정리는 모듈러 연산(modular arithmetic)에서 거듭제곱을 단순화하는 중요한 도구로, 암호학(특히 RSA 암호)에서 핵심적으로 활용됩니다.
오일러의 정리 정의
정수 \(n\)과 \(a\)가 서로소(\(\gcd(a,n)=1\))이면, 다음이 성립합니다.
\[ a^{\varphi(n)} \equiv 1 \pmod{n} \]
- \(\varphi(n)\): 오일러 피함수(Euler’s totient function), 1부터 \(n\)까지의 정수 중 \(n\)과 서로소인 수의 개수
- \(a\): \(n\)과 서로소인 양의 정수
- \(n\): 양의 정수
오일러의 정리 원리
오일러의 정리는 페르마의 소정리를 일반화한 것입니다. 페르마의 소정리는 \(n\)이 소수 \(p\)일 때 \(\varphi(p)=p-1\)로 단순화됩니다. 오일러의 정리는 \(n\)이 합성수여도 \(a\)와 \(n\)이 서로소이면 위 식이 성립합니다.
오일러 피함수 계산 방법
양의 정수 \(n\)을 소인수분해 \(n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}\) 하면,
\[ \varphi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_m}\right) \]
실제 적용 사례
1. RSA 공개키 암호
RSA 암호에서는 두 소수 \(p\), \(q\)를 선택해 \(n=pq\)를 만들고, \(\varphi(n)=(p-1)(q-1)\)을 계산합니다. 공개키 \(e\)와 비밀키 \(d\)는 다음 조건을 만족합니다.
\[ e\cdot d \equiv 1 \pmod{\varphi(n)} \]
오일러의 정리에 의해 암호화와 복호화가 서로 역연산 관계임이 보장됩니다.
2. 모듈러 거듭제곱 계산 단순화
예를 들어, \(a^{1000} \bmod 77\)을 계산할 때, \(77=7\times 11\)이므로 \(\varphi(77)=\varphi(7)\cdot\varphi(11)=6\times 10=60\)입니다. \(a\)와 77이 서로소이면 \(a^{60} \equiv 1\pmod{77}\)이므로 \(1000 \bmod 60 = 40\)만 계산하면 됩니다.
3. 반복 주기 분석
모듈러 지수 함수의 주기를 분석할 때, 오일러의 정리를 사용하면 반복 주기의 최대 길이가 \(\varphi(n)\)임을 알 수 있습니다.
4. 중국인의 나머지 정리와 결합
중국인의 나머지 정리(CRT)와 오일러의 정리를 함께 사용하면, 큰 수에 대한 모듈러 연산을 소인수분해된 작은 모듈러 연산으로 나눠 효율적으로 계산할 수 있습니다.
5. 난수 생성기 이론
선형 합동 난수 생성기(LCG)의 주기 분석에서 \(\varphi(n)\)는 최대 주기를 결정하는 핵심 요소입니다.
예제 문제
문제: \(3^{100} \bmod 35\)를 계산하라. 단, 3과 35는 서로소이다.
풀이: \(35=5\times 7\)이므로 \(\varphi(35)=(5-1)(7-1)=4\times 6=24\). 오일러의 정리에 따라 \(3^{24} \equiv 1\pmod{35}\). 100을 24로 나누면 \(100 = 24\times 4 + 4\), 따라서
\[ 3^{100} \equiv 3^4 \pmod{35} \] \(3^4 = 81\), \(81 \bmod 35 = 11\). 따라서 답은 11.
결론
정의: \(a\)와 \(n\)이 서로소이면 \(a^{\varphi(n)} \equiv 1 \ (\text{mod}\ n)\)가 성립합니다.
공식: \(\varphi(n) = n\prod_{p|n}\left(1-\frac{1}{p}\right)\), \(\gcd(a,n)=1\)일 때 \(a^{\varphi(n)}\equiv 1 \pmod{n}\).
주요 사례: RSA 암호, 모듈러 거듭제곱 단순화, 반복 주기 분석, CRT 연산 최적화, 난수 생성기 분석 등에서 사용됩니다.
오일러의 정리는 큰 수의 모듈러 연산을 효율적으로 처리하고, 현대 암호학의 수학적 기반을 제공하는 핵심 원리입니다.