홍라이프 계산기나머지(모듈러) 계산기 쉽게 이해하기 — 개념과 원리
모듈러 연산 a mod n은 a를 n으로 나눈 나머지입니다. 시계와 달력의 산술이라고 할 수 있는데, 자정에서 17시간 뒤가 5시인 것은 17 mod 12 = 5이기 때문입니다. 이 계산기는 a mod n, 거듭제곱의 나머지 aᵉ mod n, 그리고 a의 모듈러 역원을 구합니다. 정수론, 검증 숫자, 해시, RSA 같은 암호에서 가장 많이 쓰는 세 가지 연산입니다.
계산 방법
- 나머지: a mod n = a − n × ⌊a ÷ n⌋이며 항상 0부터 n − 1 사이입니다. 따라서 −7 mod 5 = 3입니다.
- 거듭제곱의 나머지: 제곱과 곱셈을 반복하는 빠른 거듭제곱으로 계산하며, 단계마다 나머지를 취하므로 수가 n²보다 커지지 않습니다.
- 모듈러 역원: a × x ≡ 1 (mod n)을 만족하는 x이며, 확장 유클리드 호제법으로 구합니다. a와 n이 서로소(gcd(a, n) = 1)일 때만 존재합니다.
원리
두 수를 n으로 나눈 나머지가 같으면 법 n에 대하여 합동이라 하고 a ≡ b (mod n)으로 씁니다. 합동은 덧셈과 곱셈에서 그대로 유지되므로 계산 도중 언제 나머지를 취해도 최종 나머지는 같습니다. 그래서 aᵉ라는 거대한 수를 만들지 않고도 aᵉ mod n을 구할 수 있습니다. 빠른 거듭제곱은 e를 2진수로 나타내 비트마다 한 번씩 제곱하므로 지수가 아주 커도 곱셈 횟수가 많지 않습니다. 역원은 베주 항등식에서 나옵니다. 확장 유클리드 호제법은 ax + ny = gcd(a, n)을 만족하는 정수 x, y를 찾아 주며, gcd가 1이면 이 식을 법 n으로 보면 ax ≡ 1이 됩니다.
예제 풀이
- 입력값: a = 17, n = 5, e = 3입니다.
- 17 ÷ 5 = 3 나머지 2이므로 17 mod 5 = 2입니다.
- 17³ ≡ 2³ = 8 ≡ 3 (mod 5)입니다. 직접 계산해도 17³ = 4,913 = 982 × 5 + 3이므로 3입니다.
- gcd(17, 5) = 1이므로 역원이 있습니다. 17 × 3 = 51 = 10 × 5 + 1이므로 역원은 3입니다.
| n (나누는 수) | a mod n |
|---|---|
| 1.25 | 0.75 |
| 2.5 | 2 |
| 3.75 | 2 |
| 5 | 2 |
| 6.25 | 4.5 |
| 7.5 | 2 |
| 10 | 7 |
결과 해석
나머지는 a가 길이 n인 주기에서 어디에 놓이는지를 알려 주며, 0이면 a가 n으로 나누어떨어진다는 뜻입니다. 모듈러 역원은 모듈러 산술에서 나눗셈 역할을 합니다. 역원이 없다고 나오면 a와 n에 공약수가 있어 a로 나눌 수 없다는 뜻입니다. n이 소수이고 a가 n의 배수가 아니면 페르마의 소정리 aⁿ⁻¹ ≡ 1 (mod n)이 성립하므로 검산에 쓸 수 있습니다. 예를 들어 2⁴ mod 5 = 1입니다.
흔한 실수
- 음수의 나머지를 음수로 기대하는 경우입니다. 자바스크립트나 C에서 −7 % 5는 −2이지만, 여기서 보여 주는 수학적 나머지는 3입니다.
- aᵉ를 먼저 다 계산한 뒤 나머지를 구해 수가 넘치는 경우입니다.
- 모든 수에 역원이 있다고 생각하는 경우입니다. 법 4에서 2의 역원은 없습니다.
- 법 n을 0으로 두는 경우입니다. 이때 연산은 정의되지 않습니다.
자주 묻는 질문
mod와 나머지는 같은 것인가요?
양수에서는 같습니다. 음수에서 수학의 mod는 항상 0부터 n − 1 사이 값을 주지만, 프로그래밍의 나머지 연산은 a의 부호를 따를 수 있습니다.
나누어떨어지는지 어떻게 확인하나요?
a mod n = 0이면 a는 n으로 나누어떨어집니다.
모듈러 역원은 어디에 쓰이나요?
3x ≡ 1 (mod 7) 같은 합동식을 푸는 데 쓰이며(x = 5), RSA에서 개인 키를 만드는 단계도 이 계산입니다.
출처: Carl Friedrich Gauss, Disquisitiones Arithmeticae (1801), Section I · Donald E. Knuth, The Art of Computer Programming, Vol. 2, §4.5.2, §4.6.3