오일러 정리

오일러 정리(Euler's theorem, 歐拉定理)는 정수론에서 오일러 피 함수를 활용하여 모듈러 산술의 거듭제곱에 대한 성질을 설명하는 정리이다. 이 정리는 페르마의 소정리를 일반화한 것으로, RSA 암호 등의 현대 암호 이론의 기초가 된다.

정리 내용

서로소인 양의 정수 a, n에 대해 다음이 성립한다. a^φ(n) ≡ 1 (mod n)

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

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

예:

• a = 3, n = 10인 경우, φ(10) = 4이고 3⁴ = 81 ≡ 1 (mod 10)

전제 조건

오일러 정리가 성립하기 위해서는 다음 조건을 만족해야 한다.

• a와 n은 서로소 (즉, gcd(a, n) = 1)
• n은 양의 정수

페르마의 소정리와의 관계

오일러 정리는 페르마의 소정리를 다음과 같이 일반화한 것이다.

• 페르마의 소정리: a^(p-1) ≡ 1 (mod p) (단, p는 소수이고 gcd(a, p) = 1)
• 오일러 정리: a^φ(n) ≡ 1 (mod n) (단, n은 임의의 양의 정수이고 gcd(a, n) = 1)

즉, p가 소수일 경우 φ(p) = p - 1이므로, 페르마의 소정리는 오일러 정리의 특수한 경우로 볼 수 있다.

증명 개요

오일러 정리는 다음과 같은 방식으로 증명할 수 있다.

• n과 서로소인 수들을 나열하고 그 집합을 S라 할 때, a와 S의 각 원소를 곱한 집합도 S와 모듈로 n에서 동치이다.
• 이 두 집합의 곱의 곱셈 결과를 비교하면, 양변에서 공통 인수들을 약분할 수 있고,
• 그 결과 a^φ(n) ≡ 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.