Lesson 19 of 20

정수론 — 나머지의 세계

소수 · 최대공약수 · 합동, 그리고 암호

지금 3시인데 20시간 뒤는 몇 시일까요? 3 + 20 = 23, 그리고 23 mod 12 = 11 — 11시입니다. 우리는 이미 나머지의 세계에서 살고 있어요.

a ≡ b (mod m) 는 "a와 b를 m으로 나눈 나머지가 같다"는 뜻이고 합동이라고 읽습니다. 9강의 언어로 말하면 동치관계예요 — 정수 전체를 나머지에 따라 m개의 조각으로 분할합니다.

여기에 두 가지 재료가 더 들어갑니다.

소수 — 1과 자기 자신으로만 나눠지는 수. 정수의 원자입니다.
최대공약수 gcd — 두 수를 동시에 나누는 가장 큰 수.

High school나머지의 세계

정수론은 가장 순수해 보이는데 가장 실용적인 분야입니다.

나눗셈의 몫이 아니라 나머지에 주목한다

왜 나머지인가

쓰임	어디
순환	요일 · 시계 · 주기
해시	테이블 크기로 나눈 나머지 ⭐
검증	체크섬 · 카드번호
암호	RSA

유한한 세계로 접어 넣는 도구다

합동 — 나머지가 같다

a ≡ b (mod n) ⟺ a − b 가 n 의 배수

예	—
17 ≡ 5 (mod 12)	시계에서 같은 자리

9강의 동치관계다 — 정수를 n 개 무리로 나눈다

비유 — 시계

—	—
15시	= 오후 3시
27시	= 오전 3시

"몇 바퀴 돌았나" 를 잊고 위치만 본다

/ca 3강의 2의 보수도 같은 발상입니다. 유한한 자릿수는 원처럼 돌아오죠.

합동은 동치관계이고, 동치관계는 집합을 분할합니다.

Python Runs in your browser

# 시계 산술 — mod 는 세상을 m개의 조각으로 나눕니다
print("지금 3시, n시간 뒤:")
for n in (5, 9, 20, 24, 100):
    print(f"   {n:>3}시간 뒤 → (3 + {n}) mod 12 = {(3 + n) % 12}시")
print()
print("mod 5 로 나눈 나머지에 따라 정수를 나눠 보면:")
for r in range(5):
    같은조 = [n for n in range(0, 26) if n % 5 == r]
    print(f"   나머지 {r}: {같은조}")
print("→ 정수 전체가 겹치지 않는 5조각으로 분할됩니다 (9강의 동치관계)")

🎮 시계와 유클리드 호제법

모듈러 계산을 시계 위에서 눈으로 보고, 유클리드 호제법이 어떻게 몇 걸음 만에 최대공약수를 찾아내는지 단계별로 따라가 보세요. 간단한 RSA 암호도 직접 돌려 볼 수 있습니다.

High school합동식이 편한 이유

나머지끼리 계산이 된다는 것이 핵심입니다.

더하기 · 빼기 · 곱하기가 나머지에서도 그대로 통한다

예로 보면

7¹⁰⁰ 을 5로 나눈 나머지는?

단계	—
7 ≡ 2 (mod 5)	—
7¹⁰⁰ ≡ 2¹⁰⁰	—
2⁴ = 16 ≡ 1	주기 발견 ⭐
2¹⁰⁰ = (2⁴)²⁵ ≡ 1²⁵ = 1	✔

거대한 수를 계산하지 않고 답을 얻는다

⚠ 나눗셈은 조심

연산	합동에서
+, −, ×	그대로 ✔
÷	조건이 필요 ⚠

예를 들어 6 ≡ 0 (mod 6) 인데 양변을 2로 나누면 3 ≢ 0 입니다.

나누는 수가 법과 서로소일 때만 나눌 수 있다

이게 암호의 열쇠입니다

—	—
서로소면	역원이 있다 — 되돌릴 수 있다
아니면	못 되돌린다

10강의 전단사 조건이 여기서 나타난다

비유 — 시계 바늘 돌리기

한 번에	12칸을 다 지나나
5칸씩 (5와 12 서로소)	전부 지난다 ✔
4칸씩 (공약수 4)	0,4,8 만 — 못 간다 ⚠

서로소여야 전체를 돌 수 있다

유클리드 호제법 — 2300년 된 알고리즘

gcd(a, b) = gcd(b, a mod b). 이 한 줄이 전부입니다. 큰 수를 작은 수로 나눈 나머지로 바꿔 가며 줄이면, 놀랍도록 빨리 끝나요.

gcd(1071, 462) → gcd(462, 147) → gcd(147, 21) → gcd(21, 0) = 21. 네 걸음입니다.

이것이 인류가 기록한 가장 오래된 알고리즘이고, 지금도 모든 암호 라이브러리 안에서 그대로 돌고 있습니다.

20자리 수의 gcd도 눈 깜짝할 사이에 구합니다.

Python Runs in your browser

def gcd(a, b, 깊이=0):
    print(f"{'  ' * 깊이}gcd({a}, {b})", end="")
    if b == 0:
        print(f"  →  {a}")
        return a
    print(f"   ({a} = {a//b}×{b} + {a % b})")
    return gcd(b, a % b, 깊이 + 1)

print("1071 과 462 의 최대공약수:")
답 = gcd(1071, 462)
print()
# 소인수분해로 구하는 것보다 훨씬 빠릅니다
import math, time
큰1, 큰2 = 987654321987654321, 123456789123456789
t = time.time()
print(f"gcd({큰1}, {큰2}) = {math.gcd(큰1, 큰2)}  ({(time.time()-t)*1000:.3f}ms)")

High school서로소와 기약분수

note 의 이 대목을 확장해 봅시다.

서로소 = 최대공약수가 1 — 더 약분할 수 없다

최대공약수 구하기 — 유클리드 호제법

2300년 된 알고리즘인데 여전히 최선입니다.

단계	—
gcd(a, b)	= gcd(b, a mod b)
반복	b 가 0 이 되면 a 가 답

12강의 점화식이다 — 그리고 아주 빠르다

얼마나 빠른가

방법	gcd(1000000, 999999)
약수를 다 찾아 비교	백만 번
호제법	2번 ✔

매번 확 줄어든다 — O(log) 다

왜 통하나

a 와 b 의 공약수는 a−b 의 약수이기도 하니까요.

—	—
d 가 a, b 를 나눈다	→ d 가 a−b 도 나눈다 ✔

공약수 집합이 안 바뀐다 — 그래서 수를 줄여도 된다

오일러 파이 함수

n 이하에서 n 과 서로소인 수의 개수를 φ(n) 이라 합니다.

계산	도구
φ(n)	17강 포함배제 ⭐

소인수의 배수를 빼고 겹침을 다시 더한다 — 정확히 포함배제다

그리고 φ(n) 이 RSA 암호의 핵심입니다. 순수 수학이 인터넷 보안이 된 거죠.

배수를 지워 나가면 소수만 남습니다.

Python Runs in your browser

# 소수 찾기 — 에라토스테네스의 체
def 체(n):
    후보 = [True] * (n + 1)
    후보[0] = 후보[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if 후보[p]:
            for x in range(p * p, n + 1, p):
                후보[x] = False
    return [i for i, v in enumerate(후보) if v]

소수들 = 체(100)
print("100 이하의 소수:", 소수들)
print(f"개수: {len(소수들)}개")
print()
for n in (1000, 10000, 100000):
    print(f"{n:>7} 이하의 소수: {len(체(n)):>6}개  (약 {len(체(n))/n*100:.1f}%)")
print("→ 커질수록 드물어지지만 결코 끝나지 않습니다 (6강 유클리드의 증명)")

RSA — 곱하기는 쉽고 되돌리기는 어렵다

두 소수 61과 53을 곱하면 3233. 1초면 됩니다. 반대로 3233을 보고 두 소수를 찾으라면? 작은 수라 금방이지만, 600자리 소수 두 개의 곱이라면 지구의 모든 컴퓨터를 동원해도 못 풉니다.

이 한쪽으로만 쉬운 성질이 RSA 암호의 전부입니다. 공개키로 잠그고(누구나 곱할 수 있고), 비밀키로만 열 수 있어요(소인수를 아는 사람만).

pow(a, b, n) 은 모듈러 거듭제곱을 아주 빠르게 계산합니다.

Python Runs in your browser

# 교과서 RSA — 아주 작은 수로 원리만 봅니다 (실제 암호로 쓰면 안 됩니다)
p, q = 61, 53
n = p * q                       # 공개
파이 = (p - 1) * (q - 1)         # 비밀
e = 17                          # 공개 지수 (파이와 서로소)
d = pow(e, -1, 파이)             # 비밀 지수 — e의 모듈러 역원

print(f"공개키 (n={n}, e={e})   비밀키 d={d}")
print(f"검산: e×d mod φ = {e*d % 파이} = 1 ✓\n")

메시지 = 123
암호 = pow(메시지, e, n)
복호 = pow(암호, d, n)
print(f"평문 {메시지} → 암호 {암호} → 복호 {복호}   {'✓ 원래대로!' if 복호 == 메시지 else '✗'}")
print(f"\n공격자는 n={n} 만 압니다. {n} = ? × ? 를 찾아야 하는데,")
print("실제 RSA 의 n 은 617자리입니다.")

High school꼭 기억하세요

19강의 정리와 암호 이야기입니다.

나머지 세계에서는 +, −, × 가 자유롭고 ÷ 만 조건부다

소수가 왜 중요한가

성질	결과
소인수분해가 유일	수의 DNA 같은 것
소수 p 로 나눈 나머지	0 빼고 전부 역원이 있다 ✔
인수분해가 어렵다	암호의 근거 ⭐

세 번째가 RSA 의 전부다

RSA 의 비대칭성

방향	난이도
큰 소수 둘을 곱한다	쉽다 — 즉시
그 곱을 인수분해한다	어렵다 — 수천 년 ⚠

한쪽만 쉬운 일방향 함수 — 10강의 그 발상이다

그런데 "어렵다" 는 증명되지 않았습니다

사실	—
빠른 방법을 아직 못 찾았다	없다고 증명은 안 됐다 ⚠
양자컴퓨터면	빠르게 풀 수 있다 (쇼어 알고리즘)

현재 인터넷 보안이 "아직 못 푼 문제" 위에 서 있다

그래서 양자내성 암호를 미리 준비하고 있습니다.

순수 수학의 쓸모

시기	—
1940년대 하디	"정수론은 어떤 실용성도 없다"
1977년	RSA — 인터넷의 기반이 됨 ⭐

쓸모없어 보이던 것이 30년 뒤 세상을 바꿨다 — 4강 섀넌과 같은 이야기

🤔 Check yourself

17 ≡ 5 (mod 6) 이 참인 이유는?

Answer 합동은 차가 m의 배수라는 뜻입니다 — 17 mod 6 = 5, 5 mod 6 = 5 로 나머지가 같아요. 나머지가 같은 수들끼리 묶는 동치관계입니다.

🤔 Check yourself

gcd(48, 18) 을 유클리드 호제법으로 구하면?

Answer gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0) = 6. 나머지로 계속 바꿔치기하면 세 걸음 만에 끝납니다 — 소인수분해를 하지 않고도요.

🤔 Check yourself

RSA 암호의 안전성이 기대고 있는 사실은?