[정수론 입문 시리즈 22편] 정수론은 어디에 쓰이고, 다음에는 무엇을 공부하면 좋을까?

정수론 시리즈 22편을 마치며, 여러분이 이제 실제로 만들 수 있는 것들을 먼저 확인해 봅시다. 가장 좋은 요약은 작은 RSA입니다. $p=5$, $q=11$만 고르면 암호화와 복호화가 손으로도 돌아갑니다.

이 작은 실험을 출발점으로, 이 시리즈가 나누어떨어짐에서 RSA, 이차 합동식까지 어떻게 이어졌는지 정리하겠습니다.

What this post covers

• 정수론 입문 시리즈 22편의 큰 흐름을 다시 요약합니다.
• 정수론이 알고리즘과 RSA 같은 암호학에 어떻게 연결되는지 설명합니다.
• 입문 이후의 학습 방향을 제안합니다.
• 시리즈 전체를 어떤 관점으로 복습하면 좋은지 정리합니다.

이번 글에서 새로 나오는 용어

• RSA: 소인수분해의 어려움과 모듈러 연산을 이용하는 대표적인 공개키 암호 방식입니다.
• 암호학 (Cryptography): 정보를 안전하게 보호하고 전달하는 방법을 연구하는 분야입니다.
• 합동 (Congruence): 같은 나머지를 가지는 관계입니다.
• 소수 (Prime Number): 정수론의 기본 블록 역할을 하는 수입니다.

시작 실험: 작은 RSA로 전체 흐름 요약하기

이 마무리 글에서는 새 공식을 하나 더 외우기보다, 앞에서 배운 도구들이 실제로 어떻게 이어지는지 손으로 작은 예를 따라가 보겠습니다.

실험 1. 최대공약수에서 역원까지

$7$의 mod $40$에서의 역원을 찾아 봅시다.

확장 유클리드 계산은 다음과 같습니다.

$$40 = 7 \times 5 + 5$$ $$7 = 5 \times 1 + 2$$ $$5 = 2 \times 2 + 1$$

역추적하면

$$1 = 5 - 2 \times 2 = 5 - (7-5)\times 2 = 3\times 5 - 2\times 7$$ $$= 3(40-7\times 5)-2\times 7 = 3\times 40 - 17\times 7$$

따라서

$$7(-17) \equiv 1 \pmod {40}$$

이고, 역원은 $23$입니다.

실험 2. 작은 RSA 모양 만들기

작은 소수 $p=5$, $q=11$을 고르면

$$n = 55, \qquad \varphi(n)=(5-1)(11-1)=40$$

입니다. 공개지수 $e=7$을 쓰면, 위 실험에서 구한 것처럼

$$d \equiv 7^{-1} \equiv 23 \pmod {40}$$

입니다.

메시지 $m=3$을 암호화하면

$$c \equiv 3^7 \pmod {55}$$

이고,

$$3^2=9, \quad 3^4=81\equiv 26 \pmod {55}$$

이므로

$$3^7=3^4\cdot 3^2\cdot 3 \equiv 26\cdot 9\cdot 3 = 702 \equiv 42 \pmod {55}$$

입니다.

실험 3. 복호화가 돌아오는지 확인

이제 $42^{23} \pmod {55}$를 계산하면 다시 $3$이 나와야 합니다. 손계산은 길어지지만, 원리는 앞에서 배운 반복제곱법과 오일러 정리의 결합입니다.

패턴 발견

위 실험에서 정수론 시리즈의 여러 조각이 한 번에 연결됩니다.

• 유클리드 호제법은 최대공약수를 구합니다.
• 확장 유클리드 알고리즘은 모듈러 역원을 구합니다.
• 오일러 피 함수는 $\varphi(n)$을 통해 지수의 주기를 알려 줍니다.
• 반복제곱법은 큰 거듭제곱을 실제로 계산 가능하게 만듭니다.
• RSA는 이 도구들을 하나의 절차로 묶습니다.

즉, 정수론의 응용은 갑자기 등장하는 것이 아니라, 작은 계산 패턴들이 차곡차곡 쌓인 결과입니다.

이론 정리

입문 정수론의 연결 지도

1. $\gcd(a,b)$를 알면 서로소 여부를 판단할 수 있습니다.
2. $\gcd(a,n)=1$이면 $a$는 mod $n$에서 역원을 가집니다.
3. $a^{\varphi(n)}\equiv 1 \pmod n$은 오일러 정리의 핵심입니다.
4. RSA에서는 $ed\equiv 1 \pmod {\varphi(n)}$가 되도록 $d$를 고릅니다.
5. 그래서 암호화 후 복호화는 $m^{ed}\equiv m \pmod n$으로 돌아옵니다.

이 요약은 이 시리즈 전체가 하나의 흐름으로 이어진다는 것을 보여 줍니다.

Python으로 확인하기

아래 코드는 위의 작은 RSA 예시를 그대로 확인합니다.

from math import gcd

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def inverse_mod(a, n):
    g, x, _ = extended_gcd(a, n)
    if g != 1:
        raise ValueError("역원이 없습니다")
    return x % n

def power_mod(base, exponent, modulus):
    result = 1
    base %= modulus
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

p, q = 5, 11
n = p * q
phi = (p - 1) * (q - 1)
e = 7
d = inverse_mod(e, phi)

m = 3
c = power_mod(m, e, n)
restored = power_mod(c, d, n)

print("n =", n)
print("phi =", phi)
print("d =", d)
print("암호문 =", c)
print("복호화 =", restored)
print("성공:", m == restored)

손계산으로 얻은 $d=23$, $c=42$가 코드에서도 확인됩니다.

정수론 입문 시리즈의 큰 흐름 다시 보기

이 시리즈의 흐름은 크게 네 단계였습니다.

1. 정수의 기본 구조 보기

• 나누어떨어짐
• 최대공약수
• 유클리드 호제법

이 단계에서는 정수 사이의 기본 관계와 구조를 읽는 법을 익혔습니다.

2. 정수해와 소수의 구조 보기

• 베주 항등식
• 1차 디오판토스 방정식
• 소수
• 소인수분해

이 단계에서는 정수해 문제와 정수의 내부 구조를 연결했습니다.

3. 합동식의 세계 보기

• 합동
• 모듈러 연산
• 모듈러 역원
• 중국인의 나머지 정리

이 단계에서는 나머지의 관점에서 정수를 다루는 새로운 언어를 배웠습니다.

4. 정리와 응용으로 확장하기

• 페르마 소정리
• 오일러 정리
• 산술함수
• 제곱잉여

이 단계에서는 정수론이 더 넓은 구조와 응용으로 이어지는 방향을 봤습니다.

정수론은 어디에 쓰일까?

1. 암호학

가장 유명한 응용은 RSA입니다. RSA는

• 큰 합성수를 소인수분해하는 일이 계산적으로 어렵다는 가정
• 오일러 피 함수와 오일러 정리
• 모듈러 연산

을 바탕으로 동작합니다.

즉, 입문 단계에서 배운 개념들이 바로 현대 암호 시스템의 기초가 됩니다.

2. 알고리즘

유클리드 호제법처럼 정수론의 많은 도구는 알고리즘 자체로도 중요합니다. 빠른 거듭제곱 계산, 역원 계산, 소수 판별 등은 실제 프로그래밍 문제에서도 자주 등장합니다.

3. 수학적 사고 훈련

정수론은 정답만 구하는 과목이 아니라, 조건을 읽고 구조를 파악하는 훈련을 제공합니다.

• 왜 서로소가 중요한가?
• 왜 어떤 식은 정수해를 가지는가?
• 왜 mod가 바뀌면 성질도 달라지는가?

이런 질문을 다루는 과정 자체가 수학적 사고를 단단하게 만듭니다.

다음에는 무엇을 공부하면 좋을까?

입문을 마친 뒤에는 크게 세 방향이 있습니다.

1. 정수론 심화

• 소수 분포
• 더 깊은 디오판토스 방정식
• 이차 상호법칙 같은 고급 주제

2. 대수와 선형대수로 확장

합동식과 구조를 더 일반적으로 보려면 대학에서 더 배우게 되는 추상대수로 확장할 수 있습니다. 그곳에서는 군, 환, 체 같은 대상을 배우지만, 지금은 “나머지 계산의 규칙을 더 넓게 일반화한다” 정도로 이해해도 충분합니다.

3. 알고리즘과 암호학으로 연결

프로그래밍에 관심이 있다면

• 빠른 거듭제곱
• 확장 유클리드 알고리즘
• RSA 구현

같은 방향으로 이어 가면 좋습니다.

복습은 어떻게 하면 좋을까?

이 시리즈를 다시 볼 때는 개별 공식보다 “연결”을 중심으로 복습하는 것이 좋습니다.

• 나누어떨어짐 → 최대공약수 → 유클리드 호제법
• 최대공약수 → 베주 항등식 → 디오판토스 방정식
• 소수 → 소인수분해 → 산술의 기본정리
• 합동 → 모듈러 연산 → 역원 → 중국인의 나머지 정리
• 페르마 소정리 → 오일러 정리

이렇게 흐름으로 기억하면 정수론이 따로 놀지 않고 하나의 구조로 보입니다.

Silverman 교재 연결

이 글은 Silverman 《친절한 수론 길라잡이》(경문사)의 다음 내용과 연결됩니다.

• 18장: RSA 공개키 암호 - 소수, 합동, 역원, 오일러 $\varphi$ 함수가 실제 암호 구조로 결합되는 대표적인 응용입니다.
• 19장: 소수 판정법 - 큰 수가 소수인지 판단하는 알고리즘적 질문으로 이어집니다.
• 22장: 이차 상호법칙 - 이차 잉여와 이차 합동식의 깊은 구조를 설명하는 핵심 주제입니다.
• 26장: 수학적 귀납법 - 4판에서 추가된 장으로, 정수론 명제를 증명하고 알고리즘의 반복 구조를 이해하는 데 필요한 증명 도구입니다.
• 관련 정리/예제: Silverman의 머리말에서 강조하듯 “이미 구현된 함수를 절대로 사용하지 말고 직접 프로그램을 만들어 보시기 바랍니다.”라는 태도는 이 시리즈의 손계산 → 패턴 → 이론 → Python 확인 흐름과 잘 맞습니다.

연습 문제

아래 점검 퀴즈에서 학습한 내용을 확인해 보세요.

Wrap-up

이번 글에서는 정수론 입문 시리즈 전체를 다시 묶어 보고, 그것이 RSA와 암호학, 알고리즘, 그리고 더 깊은 수학으로 어떻게 이어지는지 정리했습니다.

정수론은 작은 정수에서 시작하지만, 그 안에서 만나는 구조는 매우 깊고 넓습니다. 이 시리즈가 다음 공부로 넘어가는 단단한 출발점이 되면 충분합니다.