Number Theory - 수학 | AI Insight Note

정수론(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)	연립 합동

참고문헌

•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

Number Theory정수론