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

a × x ≡ 1 (mod n) 을 만족하는 정수 x 를 a 의 mod n 에서의 곱셈 역원이라고 합니다. 일반 산술의 역수(1/a)에 해당하는 모듈러 산술의 개념. 단, 역원이 존재하려면 gcd(a, n) = 1 (서로소)이어야 합니다. 예: 3 × 7 = 21 ≡ 1 (mod 10) 이므로 3 의 mod 10 역원은 7.

확장 유클리드 알고리즘이 왜 필요한가요?

두 수 a·n 의 GCD 를 구하면서 동시에 ax + ny = gcd(a, n) 을 만족하는 정수 x·y 까지 한 번에 산출하는 알고리즘. 이 x 가 곧 모듈러 역원입니다 (gcd = 1 일 때). 단순 시도(x = 1, 2, … 차례로 검사) 보다 훨씬 빠르며 큰 n 에서도 즉시 답을 얻을 수 있어요.

거듭제곱은 왜 빠른 알고리즘을 쓰나요?

a^b mod n 을 단순히 a 를 b 번 곱하면 b 가 클 때(예: b = 10^9) 매우 느리고 중간 값이 오버플로 됩니다. 빠른 거듭제곱(square-and-multiply)은 b 를 2진수로 분해해 O(log b) 단계로 끝냅니다. 매 단계 mod n 을 적용해 값이 작게 유지되므로 RSA 같은 암호 시스템에서 핵심 도구입니다.

모듈러 연산 계산기 — mod·역원·확장 유클리드·거듭제곱

모드 선택

a mod n 역원 거듭제곱

입력

a (피연산자) 정수 (음수 허용)

n (법, modulus) 1 이상 양의 정수

결과

a mod n

-

결과 값

-

gcd(a, n)

-

검증식

-

알고리즘

-

어떻게 계산하나요

1. a mod n — 단순 나머지

a mod n = a − n × ⌊a / n⌋ (항상 0 이상 n 미만)

예: 17 mod 5 = 2 (17 = 5×3 + 2). 음수 입력도 본 계산기는 0 이상으로 보정합니다 — 예: −7 mod 5 = 3 (−7 = 5×(−2) + 3). 자바스크립트의 % 는 음수 결과를 그대로 반환하므로 별도 처리.

2. 모듈러 역원 — 확장 유클리드

a × x ≡ 1 (mod n), gcd(a, n) = 1 일 때만 존재

예: 3 의 mod 10 역원 → 3 × 7 = 21 = 2×10 + 1 → x = 7. 일반 산수의 역수(1/3)에 해당하는 정수 세계의 개념입니다. RSA 암호의 키 생성에 핵심으로 쓰입니다.

3. 거듭제곱 mod — 빠른 거듭제곱

a^b mod n — square-and-multiply, O(log b)

예: 3⁶⁵ mod 7 = ? 65 = 64 + 1 = 2⁶ + 2⁰. 매 단계 제곱 후 mod 를 취해 값 폭주를 막습니다. b = 10⁹ 같은 큰 지수도 30단계 안에 끝나며, 본 계산기는 BigInt 로 정확한 결과를 보장합니다.

활용

분야	모듈러가 쓰이는 곳
암호학	RSA 공개키, 디피-헬만 키교환, 디지털 서명
해시	해시 테이블 인덱싱, 체크섬
알고리즘	큰 수 결과의 mod 1e9+7 출력 (코딩 테스트 표준)
일상	요일 계산 (n=7), 시계 산수 (n=12), ISBN 체크섬 (n=11)

한계와 주의

역원 존재 조건 — gcd(a, n) ≠ 1 이면 모듈러 역원이 존재하지 않습니다. 예: a=4, n=6 → 공약수 2 가 있어 역원 없음.
정수만 — 분수·소수 mod 는 본 계산기 범위 밖. 정수 입력으로 한정.
n ≥ 1 — n = 0 은 정의되지 않고, 음수 n 도 본 계산기는 |n| 으로 처리합니다.
큰 수 정밀도 — 거듭제곱 모드는 BigInt 로 정확. 다른 모드는 Number 안전 한계(2⁵³−1) 이내만 정확.
암호 보안 — 본 계산기는 학습·검증 용도. 실 암호 구현은 시간 공격 등 보안 고려가 필요해 표준 라이브러리를 사용해야 합니다.

모듈러 연산 계산기