yeolyi.com성열의 컴퓨터공학

255 더하기 1은 0

나머지 연산

사진 다섯 장을 넘기는 슬라이드는 다섯째 사진 다음에 다시 첫째 사진을 보입니다. 8비트 덧셈도 255 다음이 0이고, 요일도 일요일 다음이 월요일입니다. 이렇게 끝에서 처음으로 돌아오는 계산은 나눗셈의 나머지로 다룹니다.

시계 산술

10시에서 5시간이 지나면 15시가 아니라 3시입니다. 15를 12로 나누면 1바퀴 돌고 3이 남기 때문입니다.

a를 m으로 나눈 나머지는 0부터 m − 1 사이의 수입니다. 이 나머지를 구하는 계산을 나머지 연산(modulo operation)이라 하고 a mod m이라 씁니다. 15 mod 12 = 3입니다. 파이썬의 %가 이 계산입니다.

칸 수 m 12
0에서 움직인 칸 수 a 15
01234567891011
15 = 12 × 1 + 31바퀴 돌고 3칸 더 갔습니다.15 mod 12 = 3

짝수인지 가릴 때도 나머지 연산을 씁니다. a % 2가 0이면 짝수, 1이면 홀수입니다. 8비트는 256가지이니, 8비트 덧셈 a + b의 결과는 (a + b) mod 256입니다.

나머지끼리 계산하기

오늘이 수요일이면 100일 뒤는 무슨 요일일까요? 100 mod 7 = 2이니 14주는 버리고 2일만 더한 금요일입니다.

a와 b를 m으로 나눈 몫을 q₁, q₂, 나머지를 r₁, r₂라 합시다.

a = m × q₁ + r₁, b = m × q₂ + r₂

둘을 더하면 다음과 같습니다.

a + b = m × (q₁ + q₂) + (r₁ + r₂)

m의 배수는 시계를 몇 바퀴 더 돌릴 뿐이니, a + b의 나머지는 r₁ + r₂의 나머지와 같습니다.

며칠 뒤 10
다시 며칠 뒤 5
월화수목금토일
(10 + 5) mod 7 = 15 mod 7 = 1(3 + 5) mod 7 = 8 mod 7 = 1

곱하기도 풀어 쓰면 다음과 같습니다.

a × b = m × (m × q₁ × q₂ + q₁ × r₂ + q₂ × r₁) + r₁ × r₂

r₁ × r₂ 말고는 모두 m이 곱해져 있으니, a × b의 나머지도 r₁ × r₂의 나머지와 같습니다.

그래서 계산 중간중간 나머지를 구해 수를 작게 유지할 수 있습니다. 레지스터에 담기지 않을 만큼 큰 수도 나머지는 구할 수 있습니다.

3을 곱한 횟수 10
그대로 곱하면310 = 5904959049 mod 7 = 4계산 중 생기는 가장 큰 수를 담으려면 16비트 레지스터가 필요합니다.
곱할 때마다 나머지를 구하면
3264513264
계산 중 생기는 가장 큰 수가 18이라 5비트 레지스터면 됩니다.

빠른 거듭제곱

빠른 거듭제곱(exponentiation by squaring)은 지수를 이진수로 나눠 필요한 거듭제곱을 고르고, 그것들을 제곱을 거듭해 구해 곱하는 방법입니다.

예를 들어 3100을 7로 나눈 나머지를 구해 봅시다. 앞에서 본 대로 곱할 때마다 나머지만 남겨도 되지만, 하나씩 곱하면 99번의 곱셈이 필요합니다.

지수 100
거듭제곱이진수7로 나눈 나머지
36414
33212
31604
3802
3414
3202
3103
3100 = 364 × 332 × 343100 mod 7 = (4 × 2 × 4) mod 7 = 4제곱 6번과 곱셈 2번, 모두 8번 · 하나씩 곱하면 99번
  1. 표의 각 줄은 아래 줄을 제곱한 값을 7로 나눈 나머지입니다.
  2. 100은 이진수로 1100100, 곧 64 + 32 + 4이고 1에 해당하는 줄이 하이라이트되어 있습니다.
  3. 곱의 나머지는 나머지끼리 곱한 값의 나머지와 같으므로, 3100 = 364 × 332 × 34을 7로 나눈 나머지는 (4 × 2 × 4) mod 7 = 4입니다.

빠른 거듭제곱으로는 제곱 6번과 곱셈 2번, 모두 8번이면 됩니다. 지수가 두 배가 되어도 표는 한 줄만 늘어납니다. 그래서 인터넷 암호(RSA)처럼 지수가 수백 자리인 거듭제곱의 나머지도 곱셈 수천 번이면 구합니다.

도전 문제

99를 99번 곱한 수 99⁹⁹의 마지막 두 자리는 무엇일까요? 숫자로 답하세요.