모듈러 산술 해설

누구나 이미 모듈러 산술을 하고 있습니다: 8시에서 10시간 뒤는 6시이고, 일요일 다음 날은 월요일입니다. n걸음 뒤에 다시 0부터 시작하는 셈에는 나름의 완전한 산술이 있으며, 그 산술에는 규칙과 놀라움이 있고 정수론과 인터넷을 보호하는 암호학에서 중심적인 자리를 차지한다는 사실이 드러납니다.

0부터 11까지 번호가 매겨진 열두 개의 위치가 있는 시계와, 9에서 2까지 문자판을 한 바퀴 감아 도는 나선 경로
0부터 11까지 번호가 매겨진 열두 개의 위치가 있는 시계와, 9에서 2까지 문자판을 한 바퀴 감아 도는 나선 경로

나머지와 합동

a를 n으로 나누고 나머지만 남기세요: 그것이 a mod n이며, 0부터 n − 1까지의 수입니다. 26 = 3 × 7 + 5이므로 26 mod 7 = 5입니다. 나머지가 같은 수들은 mod n에서 똑같이 행동하므로 이들을 합동이라고 부릅니다: 26 ≡ 5 ≡ −2 (mod 7). 카를 프리드리히 가우스는 1801년의 저서 Disquisitiones Arithmeticae(『산술 연구』)에서 이 표기법을 도입했고, 이로써 페르마와 오일러의 오래된 관찰이 독자적인 산술이 되었습니다. n개의 위치가 있는 시계에서 모든 정수는 자신의 나머지 위치에 놓이며, 돈 바퀴 수는 잊힙니다.

카를 프리드리히 가우스, 크리스티안 알브레히트 옌센의 1840년 초상. 1801년의 Disquisitiones Arithmeticae에서 합동 기호 a ≡ b (mod n)를 도입했다.
카를 프리드리히 가우스, 크리스티안 알브레히트 옌센의 1840년 초상. 1801년의 Disquisitiones Arithmeticae에서 합동 기호 a ≡ b (mod n)를 도입했다.

덧셈, 뺄셈, 곱셈

세 가지 보통 연산은 평소처럼 작동하며, 언제든 원할 때 mod n으로 줄여도 됩니다: 합의 나머지는 나머지들의 합의 나머지이고, 차와 곱도 마찬가지입니다. 37 × 48의 일의 자리를 구하려면 일의 자리끼리만 곱하세요: 7 × 8 = 56이므로 일의 자리는 6입니다. 바로 이 점 덕분에 모듈러 산술은 컴퓨터에 매우 유용합니다: 수가 아무리 커도 중간값은 결코 n²을 넘지 않습니다.

나눗셈에는 역원이 필요합니다

나눗셈은 예외입니다. 둘 다 mod 10으로 6이므로 2 × 3 ≡ 2 × 8 (mod 10)이지만, 3과 8은 서로 다르므로 2를 그냥 약분할 수는 없습니다. a로 나눈다는 것은 그 역원, 즉 a × x ≡ 1을 만족하는 수 x를 곱한다는 뜻이며, 역원은 정확히 a와 n에 공통인수가 없을 때 존재합니다. 확장 유클리드 알고리즘이 그것을 찾아 줍니다: 최대공약수를 구하는 유클리드의 나눗셈 단계를 실행하면서 각 단계마다 승수를 기록하므로, 나머지가 1이 되었을 때의 승수가 바로 역원입니다. n이 소수이면 0을 제외한 모든 수에 역원이 있어서 나눗셈이 항상 가능합니다.

거듭제곱, 페르마와 오일러

거듭제곱은 되풀이됩니다. mod 7에서 3의 거듭제곱을 구해 보면 3, 2, 6, 4, 5, 1이 나오고 다시 3이 됩니다. 이 순환의 길이가 3의 위수입니다. 1640년 피에르 드 페르마는 소수 p에 대해 p가 a를 나누지 않으면 a^(p − 1) ≡ 1 (mod p)임을 알아차렸고, 따라서 모든 위수는 p − 1을 나눕니다. 레온하르트 오일러는 이를 증명하고, p − 1을 n과 서로소인 값의 개수로 바꾸어 임의의 n으로 확장했습니다. 거대한 거듭제곱은 반복 제곱법으로 계산합니다: a, a², a⁴, a⁸ …을 각각 바로 앞 값의 제곱으로 구해 mod n으로 줄인 다음, 지수의 이진수 자릿수에 맞게 곱합니다.

피에르 드 페르마의 초상
피에르 드 페르마의 초상
레온하르트 오일러의 초상
레온하르트 오일러의 초상

검증 숫자와 달력

모듈러 산술은 실수를 잡아냅니다. ISBN-10의 마지막 자리는 열 자리 전체의 가중합이 11의 배수가 되도록 정해지므로, 한 자리만 틀린 경우와 이웃한 두 자리가 뒤바뀐 경우가 모두 검출됩니다. 은행 카드 번호는 mod 10의 Luhn 검사를, IBAN은 mod 97의 검사를 사용합니다. 달력은 mod 7로 돌아갑니다: 어떤 날짜의 요일이든 나머지 몇 개로 구할 수 있으며, 만년력과 둠스데이 규칙이 이렇게 작동합니다.

암호학

현대 암호학은 계산하기는 쉽지만 되돌리기는 어려운 모듈러 거듭제곱 위에 세워져 있습니다. 1976년의 디피–헬먼 키 교환에서는 두 사람이 큰 소수를 법으로 하는 거듭제곱을 주고받아 공개된 회선에서 공유 비밀에 합의합니다. 1977년 리베스트, 샤미르, 애들먼이 발표한 RSA는 메시지 m을 m^e mod n으로 암호화하는데, 여기서 n은 두 큰 소수의 곱이며, 두 소수를 아는 사람만 계산할 수 있는 두 번째 지수 d로 복호화합니다. 교과서의 예에서는 n = 3233 = 61 × 53, e = 17, d = 413입니다: 65는 2790이 되고, 2790은 다시 65가 됩니다.

직접 탐구해 보세요

모듈러 시계를 열어 30자리까지의 수에 대해 a mod n과 n을 법으로 하는 합, 차, 곱, 거듭제곱, 역원, 몫을 계산해 보세요. 모든 답에는 단계가 함께 나옵니다: 나머지가 있는 나눗셈, 반복 제곱법으로 얻은 거듭제곱, 또는 확장 유클리드 알고리즘의 표입니다. 시계는 덧셈의 나선부터 거듭제곱의 순환까지 답에 어떻게 도달하는지 그려 주며, n이 작을 때는 연산표가 모든 답을 한꺼번에 보여 줍니다.

자주 묻는 질문

기호 ≡는 무슨 뜻인가요?

a ≡ b (mod n)은 a와 b를 n으로 나눈 나머지가 같다는 뜻이며, 같은 말로 n이 a − b를 나눈다는 뜻입니다. 38 − 2 = 36은 12의 배수이므로 38 ≡ 2 (mod 12)입니다.

mod는 프로그래밍의 % 연산자와 같은가요?

양수에 대해서는 그렇습니다. 음수에 대해서는 C, Java, JavaScript 같은 많은 언어가 음수 나머지를 돌려줍니다: 그런 언어에서 −7 % 3은 −1이지만, −7 mod 3 = 2입니다. Python의 %는 n이 양수일 때 수학의 관례를 따릅니다.

mod n에서 어떤 수의 위수란 무엇인가요?

a^k ≡ 1 (mod n)을 만족하는 가장 작은 k > 0입니다. 위수는 a와 n에 공통인수가 없을 때만 존재합니다. 2³ = 8 ≡ 1이므로 mod 7에서 2의 위수는 3이고, mod 7에서 3의 위수는 6이므로 3의 거듭제곱은 0이 아닌 모든 나머지를 한 번씩 거칩니다: 3은 mod 7의 원시근입니다.

모듈러 산술은 누가 만들었나요?

나머지는 훨씬 이전부터 쓰였는데, 예를 들어 3세기에서 5세기 사이의 중국인의 나머지 정리와 페르마, 오일러의 연구가 있습니다. 가우스는 1801년 합동 표기법과 함께 이를 체계적인 산술로 만들었습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

모듈러 시계 열기