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입니다. 파이썬의 %가 이 계산입니다.
짝수인지 가릴 때도 나머지 연산을 씁니다. 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₂라 합시다.
둘을 더하면 다음과 같습니다.
m의 배수는 시계를 몇 바퀴 더 돌릴 뿐이니, a + b의 나머지는 r₁ + r₂의 나머지와 같습니다.
곱하기도 풀어 쓰면 다음과 같습니다.
a × b = m × (m × q₁ × q₂ + q₁ × r₂ + q₂ × r₁) + r₁ × r₂
r₁ × r₂ 말고는 모두 m이 곱해져 있으니, a × b의 나머지도 r₁ × r₂의 나머지와 같습니다.
그래서 계산 중간중간 나머지를 구해 수를 작게 유지할 수 있습니다. 레지스터에 담기지 않을 만큼 큰 수도 나머지는 구할 수 있습니다.
빠른 거듭제곱(exponentiation by squaring)은 지수를 이진수로 나눠 필요한 거듭제곱을 고르고, 그것들을 제곱을 거듭해 구해 곱하는 방법입니다.
예를 들어 3100을 7로 나눈 나머지를 구해 봅시다. 앞에서 본 대로 곱할 때마다 나머지만 남겨도 되지만, 하나씩 곱하면 99번의 곱셈이 필요합니다.
| 거듭제곱 | 이진수 | 7로 나눈 나머지 |
|---|---|---|
| 364 | 1 | 4 |
| 332 | 1 | 2 |
| 316 | 0 | 4 |
| 38 | 0 | 2 |
| 34 | 1 | 4 |
| 32 | 0 | 2 |
| 31 | 0 | 3 |
1100100, 곧 64 + 32 + 4이고 1에 해당하는 줄이 하이라이트되어
있습니다.(4 × 2 × 4) mod 7 = 4입니다.빠른 거듭제곱으로는 제곱 6번과 곱셈 2번, 모두 8번이면 됩니다. 지수가 두 배가 되어도 표는 한 줄만 늘어납니다. 그래서 인터넷 암호(RSA)처럼 지수가 수백 자리인 거듭제곱의 나머지도 곱셈 수천 번이면 구합니다.
99를 99번 곱한 수 99⁹⁹의 마지막 두 자리는 무엇일까요? 숫자로 답하세요.