모듈러 연산 계산기 (Mod 계산기)
기본 mod, 모듈러 덧셈/뺄셈/곱셈, 모듈러 거듭제곱(빠른 거듭제곱・반복 제곱법), 모듈러 역원(확장 유클리드 호제법)의 4가지 모드를 지원하는 모듈러 연산 계산기입니다. BigInt를 사용해 음수의 mod와 매우 큰 지수의 거듭제곱도 정확하게 계산합니다.
모듈러 연산의 기본 성질
| 성질 | 설명 |
|---|---|
| (a + b) mod n = ((a mod n) + (b mod n)) mod n | 덧셈은 mod를 취한 후에 더하든, 더한 후에 mod를 취하든 결과가 같습니다. |
| (a − b) mod n = ((a mod n) − (b mod n) + n) mod n | 뺄셈은 결과가 음수가 될 수 있으므로, 마지막에 n을 더한 뒤 다시 mod n을 취해 [0, n) 범위로 맞춥니다. |
| (a × b) mod n = ((a mod n) × (b mod n)) mod n | 곱셈도 덧셈과 마찬가지로 도중에 mod를 취해도 최종 결과는 바뀌지 않습니다. 이 성질이 거듭제곱을 빠르게 계산하는 반복 제곱법의 토대가 됩니다. |
| a와 n이 서로소 ⇔ a의 n을 법으로 하는 역원이 존재한다 | 확장 유클리드 호제법으로 gcd(a, n) = 1이 되는 경우에 한해, a × x ≡ 1 (mod n)을 만족하는 x(역원)가 존재합니다. |
Tips
- 음수의 mod는 프로그래밍 언어마다 결과가 다릅니다. 이 도구는 수학적 정의(결과는 항상 0 이상 n 미만)를 따르므로 -7 mod 3은 -1이 아니라 2가 됩니다.
- 거듭제곱 모드는 "반복 제곱법"으로 계산하므로 지수가 수백 자리에 이르러도 즉시 결과를 구합니다. RSA 암호의 암호화・복호화 처리에도 같은 알고리즘이 사용됩니다.
- 시계의 시각은 우리에게 친숙한 모듈러 연산의 예입니다. "15시"를 12시간제로 바꾸면 15 mod 12 = 3시가 됩니다.
- 역원 모드는 법 n이 소수가 아니어도 a와 n이 서로소(최대공약수가 1)이기만 하면 계산할 수 있습니다.
- 경쟁적 프로그래밍에서는 거대한 답을 그대로 출력하는 대신 1,000,000,007과 같은 큰 소수로 나눈 나머지를 답으로 요구하는 문제가 자주 출제됩니다. 이 도구의 거듭제곱 모드는 그런 계산을 검산하는 데도 활용할 수 있습니다.
자주 묻는 질문
여담 ― "시계 산술"이 떠받치는 현대 암호
모듈러 연산(합동식)은 흔히 "시계 산술(clock arithmetic)"이라고 불립니다. 12시간제 시계에서 13시는 1시와 "같은" 것으로 취급되는데, 이는 정확히 13 ≡ 1 (mod 12)라는 합동식 그 자체이며, 어떤 수를 법(이 경우 12)으로 나눈 나머지에만 주목하는 사고방식입니다. 독일의 수학자 카를 프리드리히 가우스가 1801년 저서 『정수론 연구(Disquisitiones Arithmeticae)』에서 합동식 기호 "≡"를 체계화하면서, 이 개념은 현대 수학의 표준 도구가 되었습니다.
언뜻 소박해 보이는 이 연산은 현대 인터넷 보안의 근간을 떠받치고 있습니다. RSA를 비롯한 공개키 암호 방식에서는 거대한 수의 거듭제곱을 법으로 나눈 나머지를 구하는 "모듈러 지수 연산"이 암호화・복호화의 핵심 처리입니다. 지수와 법이 수백 자리에 이르기 때문에 거듭제곱을 그대로 계산한 뒤 나머지를 구하면 계산량이 폭발적으로 늘어나지만, 반복 제곱법을 사용하면 지수의 자릿수에 비례하는 횟수의 곱셈만으로 끝나 실용적인 속도로 처리할 수 있습니다.
확장 유클리드 호제법을 이용한 모듈러 역원 계산 역시 암호 이론뿐 아니라 부호 이론, 해시 함수 설계 등 컴퓨터 과학의 폭넓은 분야에서 쓰이는 기초 기술입니다. "2000년도 더 된 고대의 산술"과 "최신 보안 기술"이 같은 수학적 토대 위에 성립한다는 사실은 정수론의 보편성을 상징적으로 보여줍니다.