오일러 정리 편집하기

오일러 정리(Euler's theorem, 歐拉定理)는 정수론에서 [[오일러 피 함수]]를 활용하여 모듈러 산술의 거듭제곱에 대한 성질을 설명하는 정리이다. 이 정리는 [[페르마의 소정리]]를 일반화한 것으로, RSA 암호 등의 현대 암호 이론의 기초가 된다.
==정리 내용==
서로소인 양의 정수 a, n에 대해 다음이 성립한다. a<sup>φ(n)</sup> ≡ 1 (mod n)

여기서 φ(n)은 오일러 피 함수로, n과 서로소인 정수의 개수를 의미한다.  

* 즉, a를 n으로 나눈 나머지가 1이 되기 위해 a를 몇 번 곱해야 하는지를 오일러 피 함수가 결정한다.

예:
*a = 3, n = 10인 경우, φ(10) = 4이고 3<sup>4</sup> = 81 ≡ 1 (mod 10)
==전제 조건==
오일러 정리가 성립하기 위해서는 다음 조건을 만족해야 한다.
*a와 n은 서로소 (즉, gcd(a, n) = 1)
*n은 양의 정수
==페르마의 소정리와의 관계==
오일러 정리는 페르마의 소정리를 다음과 같이 일반화한 것이다.
*페르마의 소정리: a<sup>(p-1)</sup> ≡ 1 (mod p) (단, p는 소수이고 gcd(a, p) = 1)
*오일러 정리: a<sup>φ(n)</sup> ≡ 1 (mod n) (단, n은 임의의 양의 정수이고 gcd(a, n) = 1)
즉, p가 소수일 경우 φ(p) = p - 1이므로, 페르마의 소정리는 오일러 정리의 특수한 경우로 볼 수 있다.
==증명 개요==
오일러 정리는 다음과 같은 방식으로 증명할 수 있다.
*n과 서로소인 수들을 나열하고 그 집합을 S라 할 때, a와 S의 각 원소를 곱한 집합도 S와 모듈로 n에서 동치이다.
*이 두 집합의 곱의 곱셈 결과를 비교하면, 양변에서 공통 인수들을 약분할 수 있고,
*그 결과 a<sup>φ(n)</sup> ≡ 1 (mod n)임을 유도할 수 있다.
==응용==
*RSA 암호 알고리즘에서 비밀키 복호화의 이론적 근거로 사용된다.
*모듈러 역원 계산에 활용되며, 유클리드 알고리즘과 함께 사용하면 계산 효율이 향상된다.
*합동식의 거듭제곱 계산 시 지수법칙을 단순화하는 데 쓰인다.
==같이 보기==
*[[오일러 피 함수]]
*[[페르마의 소정리]]
*[[RSA 암호화]]
*[[합동식]]
*[[서로소]]
==참고 문헌==
*Tom M. Apostol, *Introduction to Analytic Number Theory*, Springer-Verlag, 1976.
*Kenneth H. Rosen, *Elementary Number Theory and Its Applications*, Pearson, 2010.
==각주==
[[분류:수학]]
[[분류:보안]]