모듈러 곱셈 역원 계산기

모듈러 곱셈 역원이란 무엇인가요?

법 m에 대한 정수 a의 모듈러 곱셈 역원은 [0, m-1] 범위 내에서 다음을 만족하는 정수 x입니다.

이는 a⁻¹ (mod m)으로 표기하며, 일반 산술에서의 곱셈 역원(즉, 1/a)과 유사하지만 모듈러 산술의 세계에서 정의됩니다.

핵심 조건: 역원은 gcd(a, m) = 1인 경우, 즉 a와 m이 서로소일 때만 존재합니다.

계산 방법: 확장 유클리드 알고리즘

가장 효율적인 방법은 확장 유클리드 알고리즘을 사용하는 것입니다. 이 알고리즘은 베주 항등식을 만족하는 정수 x와 y를 찾습니다.

gcd(a, m) = 1일 때, 양변에 mod m을 취하면 a·x ≡ 1 (mod m)이 되므로 x가 모듈러 역원이 됩니다.

예시: 3⁻¹ (mod 7) 구하기:

확장 GCD 결과: 3·(5) + 7·(-2) = 15 − 14 = 1이므로, 3⁻¹ ≡ 5 (mod 7)입니다. 검증: 3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7) ✓

암호학 및 수학에서의 활용

자주 묻는 질문(FAQ)