정수론(Number Theory)은 정수의 성질을 연구하는 가장 오래된 수학 분야다. "순수 호기심의 학문"에서 출발해 현재는 RSA·타원 곡선 암호·해시 함수·의사난수 생성의 핵심 수학을 제공한다.
1. 산술의 기본 정리
모든 양의 정수 n > 1은 소수의 곱으로 유일하게 표현된다.
n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ
예) 360 = 2³ × 3² × 5¹
약수 개수·합 공식
n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ 일 때:
약수 개수: τ(n) = (a₁+1)(a₂+1)···(aₖ+1)
약수 합: σ(n) = (p₁^(a₁+1)-1)/(p₁-1) × ··· × (pₖ^(aₖ+1)-1)/(pₖ-1)
예) 360 = 2³ × 3² × 5¹
τ(360) = (3+1)(2+1)(1+1) = 24
σ(360) = (2⁴-1)/(2-1) × (3³-1)/(3-1) × (5²-1)/(5-1)
= 15 × 13 × 6 = 1170
완전수: σ(n) = 2n (예: 6, 28, 496)
2. 소수 (Prime Numbers)
소수는 1과 자기 자신만을 약수로 갖는 1보다 큰 정수다.
소수의 무한성: 유한하다고 가정하면 p₁p₂···pₖ + 1은 기존 소수들로 나눠지지 않는다 → 모순 (유클리드)
소수 판정법
에라토스테네스의 체 — n 이하 소수 전체를 O(n log log n)에 구한다.
python
def sieve(n: int) -> list[int]:
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i in range(2, n+1) if is_prime[i]]
print(sieve(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
밀러-라빈 소수 판별 — 확률적 판별, 대형 소수에 사용
python
def miller_rabin(n: int, k: int = 10) -> bool:
if n < 2: return False
if n in (2, 3): return True
if n % 2 == 0: return False
r, d = 0, n - 1 # n-1 = 2^r × d
while d % 2 == 0:
r += 1
d //= 2
import random
for _ in range(k):
a = random.randrange(2, n - 1)
x = pow(a, d, n)
if x in (1, n - 1):
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True # 높은 확률로 소수
def generate_prime(bits: int) -> int:
import random
while True:
n = random.getrandbits(bits) | (1 << bits - 1) | 1
if miller_rabin(n):
return n
소수 정리: n 이하 소수의 개수 π(n) ≈ n / ln(n)
3. 유클리드 호제법
gcd(a, b) = gcd(b, a mod b) (b = 0 이면 a 반환)
예) gcd(252, 105):
gcd(252, 105) = gcd(105, 42) = gcd(42, 21) = gcd(21, 0) = 21
lcm(a, b) = a × b / gcd(a, b)
라메 정리: 유클리드 알고리즘의 단계 수는 O(log min(a,b))
python
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
def lcm(a: int, b: int) -> int:
return a * b // gcd(a, b)
확장 유클리드 호제법 (베주 항등식)
임의의 정수 a, b에 대해 ax + by = gcd(a, b) 를 만족하는 정수 x, y가 존재한다.
python
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""gcd(a,b), x, y 반환 — ax + by = gcd(a,b)"""
if b == 0:
return a, 1, 0
g, x, y = extended_gcd(b, a % b)
return g, y, x - (a // b) * y
# 예: 252x + 105y = gcd(252, 105) = 21
g, x, y = extended_gcd(252, 105)
print(f"gcd={g}, x={x}, y={y}") # gcd=21, x=-2, y=5
# 검증: 252×(-2) + 105×5 = -504 + 525 = 21
4. 합동식과 모듈러 산술
합동 (Congruence): a ≡ b (mod m) ⟺ m | (a - b)
성질:
반사성: a ≡ a (mod m)
대칭성: a ≡ b → b ≡ a (mod m)
추이성: a ≡ b, b ≡ c → a ≡ c (mod m)
덧셈: a ≡ b, c ≡ d → a+c ≡ b+d (mod m)
곱셈: a ≡ b, c ≡ d → ac ≡ bd (mod m)
나눗셈: ac ≡ bc (mod m) → a ≡ b (mod m/gcd(c,m))
(주의: gcd(c,m)=1 일 때만 그냥 나눌 수 있음)
모듈러 역원
a × a⁻¹ ≡ 1 (mod m) — gcd(a, m) = 1 일 때 존재한다.
python
def mod_inverse(a: int, m: int) -> int:
g, x, _ = extended_gcd(a % m, m)
if g != 1:
raise ValueError(f"역원 없음: gcd({a},{m}) = {g}")
return x % m
# 예: 3⁻¹ mod 7 = ?
print(mod_inverse(3, 7)) # 5 (3×5 = 15 ≡ 1 mod 7)
선형 합동식
ax ≡ b (mod m) 의 해: gcd(a, m) | b 일 때 gcd(a, m)개의 해가 존재
해법:
1. g = gcd(a, m) 계산
2. g ∤ b 이면 해 없음
3. 양변을 g로 나눠 (a/g)x ≡ (b/g) (mod m/g) 로 단순화
4. 확장 유클리드로 (a/g)⁻¹ mod (m/g) 계산
5. 중국인의 나머지 정리 (CRT)
서로소인 m₁, m₂, …, mₖ에 대해 연립 합동식은 모듈러 M = m₁m₂···mₖ 범위에서 유일한 해를 가진다.
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)
python
def crt(remainders: list[int], moduli: list[int]) -> int:
"""중국인의 나머지 정리 — 연립 합동식 해 반환"""
M = 1
for m in moduli:
M *= m
x = 0
for ai, mi in zip(remainders, moduli):
Mi = M // mi
x += ai * Mi * mod_inverse(Mi, mi)
return x % M
# 예: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
print(crt([2, 3, 2], [3, 5, 7])) # 23
6. 오일러 피 함수 φ(n)
1부터 n까지 n과 서로소인 정수의 개수.
계산 공식 (소인수분해 이용):
φ(n) = n × Π(1 - 1/p) (곱은 n의 소인수 p에 대해)
예) φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 4
12와 서로소인 수: {1, 5, 7, 11}
성질:
p 소수: φ(p) = p - 1
φ(pⁿ) = pⁿ - p^(n-1) = pⁿ(1 - 1/p)
곱셈성: gcd(m,n)=1 → φ(mn) = φ(m)φ(n)
합 공식: Σ_{d|n} φ(d) = n
python
def euler_phi(n: int) -> int:
result = n
p = 2
temp = n
while p * p <= temp:
if temp % p == 0:
while temp % p == 0:
temp //= p
result -= result // p
p += 1
if temp > 1:
result -= result // temp
return result
print(euler_phi(12)) # 4
print(euler_phi(100)) # 40
7. 페르마 소정리 & 오일러 정리
페르마 소정리: p 소수이고 gcd(a, p) = 1 이면
a^(p-1) ≡ 1 (mod p)
→ a^p ≡ a (mod p)
오일러 정리 (페르마 소정리의 일반화): gcd(a, n) = 1 이면
a^φ(n) ≡ 1 (mod n)
빠른 거듭제곱 (반복 제곱법):
python
def fast_pow(base: int, exp: int, mod: int) -> int:
"""O(log exp) 모듈러 지수"""
result = 1
base %= mod
while exp > 0:
if exp & 1:
result = result * base % mod
exp >>= 1
base = base * base % mod
return result
# 페르마 소정리 검증: 3^6 mod 7 = 1
print(fast_pow(3, 6, 7)) # 1
8. 이차잉여와 르장드르 기호
p가 홀수 소수이고 gcd(a, p) = 1 일 때:
르장드르 기호 (a/p):
1 : a가 mod p 이차잉여 (x² ≡ a (mod p) 의 해 존재)
-1 : 이차비잉여
0 : p | a
오일러 판정법:
(a/p) ≡ a^((p-1)/2) (mod p)
이차 상호법칙 (가우스):
홀수 소수 p ≠ q에 대해
(p/q)(q/p) = (-1)^((p-1)/2 × (q-1)/2)
보충법칙:
(-1/p) = (-1)^((p-1)/2) → p ≡ 1 (mod 4) 이면 1
(2/p) = (-1)^((p²-1)/8) → p ≡ ±1 (mod 8) 이면 1
python
def legendre(a: int, p: int) -> int:
"""르장드르 기호 (a/p)"""
val = fast_pow(a, (p - 1) // 2, p)
return -1 if val == p - 1 else val
print(legendre(2, 7)) # 1 (3² = 9 ≡ 2 mod 7)
print(legendre(3, 7)) # -1 (이차비잉여)
9. 원시근과 이산 로그
위수 (Order): gcd(a, n) = 1 일 때 a^k ≡ 1 (mod n) 을 만족하는 최소 양의 정수 k. ord_n(a)로 표기.
원시근 (Primitive Root): ord_p(g) = p - 1 인 g. 모든 소수 p에 대해 원시근이 존재한다.
p=7의 원시근 g=3:
3¹ ≡ 3, 3² ≡ 2, 3³ ≡ 6, 3⁴ ≡ 4, 3⁵ ≡ 5, 3⁶ ≡ 1 (mod 7)
→ {1,2,3,4,5,6} 전체 생성
이산 로그 문제: g^x ≡ h (mod p) 에서 x를 구하는 것. 효율적 알고리즘이 없어 Diffie-Hellman·ElGamal 암호의 안전성 근거.
10. 산술 함수
| 함수 | 정의 | 예시 |
|---|
| τ(n) | 약수 개수 | τ(6)=4 |
| σ(n) | 약수 합 | σ(6)=12 |
| φ(n) | 서로소 개수 (오일러 피) | φ(6)=2 |
| μ(n) | 뫼비우스 함수 | μ(6)=1 |
| Λ(n) | 폰 망골트 함수 | Λ(p^k)=ln p |
뫼비우스 함수 μ(n):
μ(1) = 1
μ(n) = 0 (n이 완전제곱 인수 포함 시)
μ(n) = (-1)^k (n = p₁p₂···pₖ, 서로 다른 소수의 곱)
예) μ(1)=1, μ(2)=-1, μ(4)=0, μ(6)=1, μ(30)=-1
뫼비우스 반전 공식:
g(n) = Σ_{d|n} f(d) ⟺ f(n) = Σ_{d|n} μ(n/d) g(d)
11. 디오판토스 방정식
정수 해를 구하는 방정식.
일차 디오판토스 방정식: ax + by = c
해의 존재 조건: gcd(a, b) | c
해법:
1. g = gcd(a, b), 확장 유클리드로 ax₀ + by₀ = g 해 구하기
2. c/g 배하면 a(x₀c/g) + b(y₀c/g) = c
3. 일반해: x = x₀c/g + (b/g)t, y = y₀c/g - (a/g)t (t ∈ ℤ)
피타고라스 세 쌍 (x² + y² = z²):
원시 피타고라스 세 쌍의 매개변수화 (m > n > 0, gcd(m,n)=1, m-n 홀수):
x = m² - n², y = 2mn, z = m² + n²
예) m=2, n=1 → (3, 4, 5)
m=3, n=2 → (5, 12, 13)
m=4, n=1 → (15, 8, 17)
12. RSA 암호
오일러 정리를 기반으로 하는 공개키 암호 시스템.
python
def rsa_demo():
# 1. 키 생성
p, q = 61, 53
n = p * q # 공개 모듈러스 = 3233
phi = (p-1) * (q-1) # = 3120
e = 17 # 공개 지수 (1 < e < phi, gcd(e,phi)=1)
d = mod_inverse(e, phi) # 개인 지수
# 2. 암호화: C = M^e mod n
M = 65
C = fast_pow(M, e, n) # C = 2790
# 3. 복호화: M = C^d mod n
decrypted = fast_pow(C, d, n)
print(f"원문: {M}, 암호: {C}, 복호: {decrypted}")
# → 원문: 65, 암호: 2790, 복호: 65
rsa_demo()
정확성 증명 (오일러 정리):
ed ≡ 1 (mod φ(n)) 이므로 C^d = (M^e)^d = M^(ed) = M^(kφ(n)+1) ≡ M (mod n)
안전성: n의 소인수분해가 어렵기 때문에 d를 구하기 어렵다.
알고리즘 복잡도 요약
| 알고리즘 | 시간 복잡도 | 용도 |
|---|
| 유클리드 호제법 | O(log min(a,b)) | GCD |
| 확장 유클리드 | O(log min(a,b)) | 모듈러 역원, 베주 계수 |
| 빠른 거듭제곱 | O(log exp) | 모듈러 지수, RSA |
| 에라토스테네스의 체 | O(n log log n) | n 이하 소수 전체 |
| 밀러-라빈 판별 | O(k log² n) | 대형 소수 판정 |
| 오일러 피 함수 | O(√n) | φ(n) 계산 |
| 중국인의 나머지 | O(k log M) | 연립 합동 |
관련 개념
- •암호학 — 정수론의 핵심 응용 분야
- •RSA — 오일러 정리 기반 공개키 암호
- •조합론 — 정수론과 연계된 이산 수학
- •알고리즘 — 유클리드·밀러-라빈 등 정수론 알고리즘 구현
참고문헌
- •Hardy, G.H. & Wright, E.M. An Introduction to the Theory of Numbers
- •민zkn. Number Theory — 정수론 종합 교육 자료
- •Knuth, D.E. The Art of Computer Programming, Vol. 2