모듈로 역원

모듈러 역원(Modular Inverse, 模組逆元)은 정수 a와 양의 정수 m에 대해 ax ≡ 1 (mod m)를 만족하는 정수 x를 의미한다.

1 개요

모듈러 역원은 모듈로 연산 체계에서 나눗셈을 정의하는 데 사용되는 개념이다. 정수 a가 모듈러 m에 대해 역원을 가지기 위해서는 a와 m이 서로소, 즉 gcd(a, m) = 1이어야 한다. 모듈러 역원은 암호학, 수론, 알고리즘 등 다양한 분야에서 필수적으로 활용된다.

2 정의

정수 a에 대해 다음을 만족하는 정수 x를 모듈러 m에서의 a의 역원이라 한다.

ax ≡ 1 (mod m)

3 구하는 방법

모듈러 역원은 다음과 같은 방법으로 구할 수 있다.

3.1 확장 유클리드 알고리즘 이용

확장 유클리드 알고리즘을 사용하면 ax + my = 1을 만족하는 (x, y)를 구할 수 있으며, 이때 x를 m에 대해 나눈 나머지가 모듈러 역원이 된다.

3.2 페르마의 소정리 이용

m이 소수일 경우, a^(m-2) ≡ a^(-1) (mod m)이라는 페르마의 소정리를 이용하여 모듈러 역원을 계산할 수 있다.

4 예시

모듈러 26에 대해 7의 역원을 구하는 과정은 다음과 같다.

1. 확장 유클리드 알고리즘으로 7x + 26y = 1을 푼다.
2. 26 ÷ 7 = 3 (나머지 5)
3. 7 ÷ 5 = 1 (나머지 2)
4. 5 ÷ 2 = 2 (나머지 1)
5. 2 ÷ 1 = 2 (나머지 0)

역추적하여 계수를 구하면,

1. 1 = 5 - 2×2
2. 1 = 5 - 2×(7 - 5×1) = 3×5 - 2×7
3. 1 = 3×(26 - 7×3) - 2×7 = 3×26 - 11×7

따라서 x = -11, 즉 26을 더해 15가 된다.

결론적으로 7의 모듈러 26에 대한 역원은 15이다.

5 특성

• a와 m이 서로소일 때만 역원이 존재한다.
• 모듈러 역원은 항상 0 이상 m-1 이하의 값을 갖는다.
• 역원이 존재하면 유일하다(mod m 기준).

6 활용

• RSA 암호 알고리즘 키 생성 및 해독
• 선형 합동 방정식의 해 구하기
• 중국인의 나머지 정리(Chinese Remainder Theorem) 적용
• 암호 프로토콜 및 블록체인 시스템 내 연산 최적화

7 같이 보기

• 확장 유클리드 알고리즘
• 유클리드 알고리즘
• 페르마의 소정리
• RSA 암호 알고리즘
• 모듈로 연산

8 참고 문헌

• Rosen, Kenneth H. *Elementary Number Theory and Its Applications*. Pearson, 2010.
• Koblitz, Neal. *A Course in Number Theory and Cryptography*. Springer, 1994.