2장. 정수론 개론

암호학은 정수론 위에 세워져 있다. 이 장은 이후 장(유한체, 공개키 암호)을 이해하기 위한 기반을 다룬다.

학습 목표

• 가분성과 나눗셈 알고리즘을 이해한다.
• 유클리드 알고리즘으로 최대공약수를 구한다.
• 모듈러 산술과 확장 유클리드 알고리즘을 다룬다.
• 소수, 페르마 정리, 오일러 정리, 오일러 토티언트 함수를 설명한다.
• 밀러–라빈 소수 판정, 중국인의 나머지 정리, 이산 로그를 이해한다.

---

2.1 가분성과 나눗셈 알고리즘

가분성 (Divisibility)

정수 $a, b, m$에 대해 $a = mb$ ($b \neq 0$) 이면 "$b$가 $a$를 나눈다"라 하고 $b \mid a$로 표기.

가분성의 주요 성질

• $a \mid 1 \;\Rightarrow\; a = \pm 1$
• $a \mid b$ 이고 $b \mid a$ 이면 $a = \pm b$
• $b \neq 0$ 이면 $b \mid 0$
• $a \mid b$ 이고 $b \mid c$ 이면 $a \mid c$ (이행성)
• $b \mid g$ 이고 $b \mid h$ 이면 임의의 정수 $m, n$에 대해 $b \mid (mg + nh)$

나눗셈 알고리즘 (Division Algorithm)

임의의 정수 $a$와 양의 정수 $n$에 대해, 다음을 만족하는 유일한 정수 $q$(몫)와 $r$(나머지)가 존재한다.

$$a = qn + r, \quad 0 \le r < n, \quad q = \lfloor a/n \rfloor$$

$r$은 잉여(residue) 라고도 부른다.

예시

• $a = 11,\ n = 7$: $11 = 1 \cdot 7 + 4,\ q = 1,\ r = 4$
• $a = -11,\ n = 7$: $-11 = (-2) \cdot 7 + 3,\ q = -2,\ r = 3$

---

2.2 유클리드 알고리즘

최대공약수 (GCD)

두 정수 $a, b$를 모두 나누는 가장 큰 양의 정수를 $\gcd(a, b)$로 표기.

• $\gcd(a, b) = \gcd(|a|, |b|)$
• $\gcd(a, 0) = |a|$
• $\gcd(a, b) = 1$ 이면 서로소(relatively prime)

유클리드 알고리즘의 핵심 정리

$$\gcd(a, b) = \gcd(b,\ a \bmod b)$$

이 관계를 반복 적용하여 $\gcd$를 구한다.

재귀 정의

Euclid(a, b):
    if b == 0: return a
    else: return Euclid(b, a mod b)

예시: $\gcd(1160718174,\ 316258250) = 1078$

단계	피제수	제수	몫	나머지
1	1,160,718,174	316,258,250	3	211,943,424
2	316,258,250	211,943,424	1	104,314,826
3	211,943,424	104,314,826	2	3,313,772
…	…	…	…	…
10	2,156	1,078	2	0

---

2.3 모듈러 산술

Modulus와 합동 (Congruence)

정수 $a$, 양의 정수 $n$에 대해 $a \bmod n$은 $a$를 $n$으로 나눈 나머지.

$$a \equiv b \pmod{n} \iff n \mid (a - b)$$

합동 관계의 성질

1. $a \equiv b \pmod{n}$ iff $n \mid (a - b)$
2. $a \equiv b \pmod{n}$ 이면 $b \equiv a \pmod{n}$
3. $a \equiv b,\ b \equiv c \pmod{n}$ 이면 $a \equiv c \pmod{n}$

모듈러 산술 연산의 성질

$$[(a \bmod n) + (b \bmod n)] \bmod n = (a + b) \bmod n$$ $$[(a \bmod n) - (b \bmod n)] \bmod n = (a - b) \bmod n$$ $$[(a \bmod n) \times (b \bmod n)] \bmod n = (a \times b) \bmod n$$

빠른 모듈러 거듭제곱 예시: $11^7 \bmod 13$

$$\begin{aligned} 11^2 &= 121 \equiv 4 \pmod{13} \\ 11^4 &= (11^2)^2 \equiv 16 \equiv 3 \pmod{13} \\ 11^7 &= 11 \cdot 11^2 \cdot 11^4 \equiv 11 \cdot 4 \cdot 3 \equiv 132 \equiv 2 \pmod{13} \end{aligned}$$

잉여류 집합 $\mathbb{Z}_n$

$$\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}$$

$\mathbb{Z}_n$은 단위원을 갖는 가환환(commutative ring) 이다.

곱셈 소거 법칙 (주의)

보통의 산술과 달리, 모듈러 산술에서 곱셈 소거는 조건부로만 성립한다.

$$a \cdot b \equiv a \cdot c \pmod{n} \;\Rightarrow\; b \equiv c \pmod{n}, \quad \text{단, } \gcd(a, n) = 1$$

$a$가 $n$과 서로소일 때만 $a$의 곱셈 역원이 존재한다.

확장 유클리드 알고리즘 (Extended Euclidean)

$\gcd$ 뿐 아니라 베주 계수(Bézout coefficients) $x, y$도 함께 구한다.

$$ax + by = \gcd(a, b)$$

반복 과정에서 다음 점화식을 유지한다.

$$x_i = x_{i-2} - q_i x_{i-1}, \qquad y_i = y_{i-2} - q_i y_{i-1}$$

활용: $a$의 모듈러 역원 $a^{-1} \bmod n$은 $ax + ny = 1$을 풀어 $x$로 구한다. 이는 RSA 키 생성, 유한체 연산에서 핵심적으로 사용된다.

예시: $1759x + 550y = \gcd(1759, 550)$

$i$	$r_i$	$q_i$	$x_i$	$y_i$
-1	1759	—	1	0
0	550	—	0	1
1	109	3	1	-3
2	5	5	-5	16
3	4	21	106	-339
4	1	1	-111	355

결과: $\gcd = 1,\ x = -111,\ y = 355$

---

2.4 소수

$p > 1$인 정수가 $\pm 1, \pm p$ 외의 약수를 갖지 않으면 소수(prime) 이다.

산술의 기본 정리

임의의 정수 $a > 1$은 소수의 곱으로 유일하게 분해된다.

$$a = p_1^{a_1} p_2^{a_2} \cdots p_t^{a_t}, \qquad p_1 < p_2 < \cdots < p_t$$

또는 모든 소수 $p \in P$에 대해

$$a = \prod_{p \in P} p^{a_p}, \qquad a_p \ge 0$$

소인수분해로 보는 gcd

$a = \prod p^{a_p},\ b = \prod p^{b_p}$ 일 때

$$\gcd(a, b) = \prod_{p \in P} p^{\min(a_p,\, b_p)}$$

단, 소인수분해 자체가 어렵기 때문에 이 공식은 실용적 계산법이 아니다. 실제로는 유클리드 알고리즘을 사용한다.

---

2.5 페르마 정리와 오일러 정리

페르마의 작은 정리 (Fermat's Little Theorem)

$p$가 소수이고 $\gcd(a, p) = 1$ 이면

$$a^{p-1} \equiv 1 \pmod{p}$$

대안형 ($a$가 $p$로 나누어져도 성립):

$$a^p \equiv a \pmod{p}$$

예시: $p = 19,\ a = 7 \Rightarrow 7^{18} \equiv 1 \pmod{19}$

오일러 토티언트 함수 $\phi(n)$

$1$부터 $n-1$까지의 정수 중 $n$과 서로소인 것의 개수. 관례상 $\phi(1) = 1$.

핵심 공식

조건	공식
$p$가 소수	$\phi(p) = p - 1$
$p$가 소수, $k \ge 1$	$\phi(p^k) = p^k - p^{k-1}$
$\gcd(m, n) = 1$	$\phi(mn) = \phi(m)\,\phi(n)$
$p, q$가 서로 다른 소수, $n = pq$	$\phi(n) = (p-1)(q-1)$

마지막 공식은 RSA의 키 생성 에서 직접 사용된다.

오일러 정리

$\gcd(a, n) = 1$ 이면

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

대안형:

$$a^{\phi(n)+1} \equiv a \pmod{n}$$

페르마 정리는 오일러 정리의 특수한 경우 ($n = p$ 소수)이다.

---

2.6 소수 판정 (Primality Testing)

밀러–라빈 알고리즘 (Miller–Rabin)

암호학에서 가장 널리 쓰이는 확률적 소수 판정 알고리즘.

핵심 성질

성질 1: $p$가 소수이고 $0 < a < p$ 이면

$$a^2 \equiv 1 \pmod{p} \iff a \equiv \pm 1 \pmod{p}$$

성질 2: $p > 2$가 소수일 때 $p - 1 = 2^k q$ ($q$는 홀수)로 표현하면, $1 < a < p-1$인 임의의 $a$에 대해 다음 중 하나가 반드시 성립.

1. $a^q \equiv 1 \pmod{p}$
2. 어떤 $j\ (0 \le j \le k-1)$에 대해 $a^{2^j q} \equiv -1 \pmod{p}$

알고리즘

TEST(n):
    find k > 0, q odd such that (n - 1) = 2^k · q
    pick random a with 1 < a < n - 1
    if a^q mod n == 1: return "inconclusive"
    for j = 0 to k - 1:
        if a^(2^j · q) mod n == n - 1: return "inconclusive"
    return "composite"

• composite 반환 → $n$은 확실히 합성수
• inconclusive 반환 → $n$은 아마도 소수 (결정적이지 않음)

반복 사용과 정확도

$n$이 합성수이지만 한 번의 TEST에서 inconclusive를 반환할 확률은 $< 1/4$. $t$번 반복 시 모두 통과할 확률은

$$< (1/4)^t$$

예: $t = 10$이면 $10^{-6}$ 미만.

AKS 알고리즘 (결정적)

2002년 Agrawal–Kayal–Saxena가 발표한 결정적 다항시간 소수 판정 알고리즘. 이론적으로 획기적이지만, 실제 성능은 여전히 밀러–라빈보다 느려 실무에서는 밀러–라빈이 주로 사용된다.

소수의 분포 (소수 정리)

$n$ 근처에서 소수는 평균적으로 $\ln(n)$마다 하나씩 존재. 짝수를 제외하면 평균 $0.5 \ln(n)$번 시도 후 소수 발견.

$2^{200}$ 크기의 소수를 찾으려면 평균 $0.5 \ln(2^{200}) \approx 69$번 시도.

---

2.7 중국인의 나머지 정리 (CRT)

서로 쌍으로 서로소인 $m_1, m_2, \ldots, m_k$에 대해 $M = \prod_{i=1}^{k} m_i$라 하자.

$\mathbb{Z}_M$의 임의의 원소 $A$는 다음 $k$-튜플과 일대일 대응한다.

$$A \leftrightarrow (a_1, a_2, \ldots, a_k), \qquad a_i = A \bmod m_i$$

복원 공식

$M_i = M/m_i$, $c_i = M_i \cdot (M_i^{-1} \bmod m_i)$ 로 정의할 때

$$A \equiv \sum_{i=1}^{k} a_i c_i \pmod{M}$$

합동 연산은 튜플별 연산으로 환원

$$(A \pm B) \bmod M \leftrightarrow \big((a_1 \pm b_1) \bmod m_1,\ \ldots,\ (a_k \pm b_k) \bmod m_k\big)$$ $$(A \cdot B) \bmod M \leftrightarrow \big((a_1 \cdot b_1) \bmod m_1,\ \ldots,\ (a_k \cdot b_k) \bmod m_k\big)$$

응용

큰 수 $M$에 대한 연산을 작은 $m_i$들에 대한 연산으로 분해할 수 있다. RSA 복호화 가속(CRT 최적화)의 핵심 원리.

예시 (손자의 문제): $x \equiv 2 \pmod 3,\ x \equiv 3 \pmod 5,\ x \equiv 2 \pmod 7 \Rightarrow x = 23$

---

2.8 이산 로그 (Discrete Logarithms)

정수의 차수 (Order)

$\gcd(a, n) = 1$일 때 $a^m \equiv 1 \pmod n$을 만족하는 가장 작은 양의 정수 $m$을 $a$의 차수(order) 라 한다. $m$은 항상 $\phi(n)$을 나눈다.

원시근 (Primitive Root)

차수가 $\phi(n)$인 정수를 $n$의 원시근이라 한다. $a$가 $n$의 원시근이면

$$a,\ a^2,\ a^3,\ \ldots,\ a^{\phi(n)}$$

는 서로 다른 (mod $n$) 값이고, 모두 $n$과 서로소.

• 원시근을 갖는 정수 $n$은 $2, 4, p^k, 2p^k$ 형태뿐 ($p$는 홀수 소수).
• 소수 $p$는 항상 원시근을 갖는다.

이산 로그의 정의

$a$가 소수 $p$의 원시근이면, 임의의 $b$에 대해 유일한 $i\ (0 \le i \le p-2)$가 존재해

$$b \equiv a^i \pmod{p}$$

이 $i$를 $b$의 $a$를 밑으로 하는 이산 로그라 하고 $\operatorname{dlog}_{a, p}(b)$ 또는 $\operatorname{ind}_{a, p}(b)$로 표기.

로그 성질의 유사성

$$\operatorname{dlog}_{a, p}(xy) \equiv \operatorname{dlog}_{a, p}(x) + \operatorname{dlog}_{a, p}(y) \pmod{\phi(p)}$$ $$\operatorname{dlog}_{a, p}(y^r) \equiv r \cdot \operatorname{dlog}_{a, p}(y) \pmod{\phi(p)}$$

이산 로그 문제 (DLP)

$y = g^x \bmod p$에서

• $g, x, p$로 $y$ 계산 → 쉬움 (빠른 거듭제곱, Chapter 9)
• $y, g, p$로 $x$ 계산 → 매우 어려움

현재 가장 빠른 알고리즘의 점근적 복잡도:

$$O\!\left( \exp\!\left( (\ln p)^{1/3} (\ln \ln p)^{2/3} \right) \right)$$

이 일방향성이 Diffie–Hellman 키 교환, ElGamal, DSA 등의 보안을 지탱한다.

---

부록 2A. Mod의 두 가지 의미

mod는 두 가지 방식으로 사용된다.

이항 연산자로서의 mod

$$a \bmod n = a - \lfloor a/n \rfloor \cdot n, \quad n \neq 0$$

두 정수를 받아 나머지를 반환. 예: $7 \bmod 3 = 1$.

합동 관계로서의 mod

$$a \equiv b \pmod{n} \iff a \bmod n = b \bmod n \iff n \mid (a - b)$$

괄호 사용이 다름에 유의:

• 이항 연산자: a mod n (괄호 없음)
• 합동 관계: a ≡ b (mod n) (괄호 안에 modulus)

---

주요 용어

한글	영문
전단사	bijection
합성수	composite number
중국인의 나머지 정리	Chinese remainder theorem
이산 로그	discrete logarithm
약수	divisor
유클리드 알고리즘	Euclidean algorithm
오일러 정리	Euler's theorem
오일러 토티언트 함수	Euler's totient function
페르마 정리	Fermat's theorem
최대공약수	greatest common divisor (gcd)
모듈러 산술	modular arithmetic
법, 모듈러스	modulus
차수	order
소수	prime number
원시근	primitive root
서로소	relatively prime
잉여	residue