정수론

1. 유클리드 호제법 (GCD & LCM)

최대공약수(GCD)와 최소공배수(LCM)를 빠르게 구하는 알고리즘

GCD(최대공약수): gcd(a, b) = gcd(b, a % b)

LCM(최소공배수): lcm(a, b) = (a * b) // gcd(a, b)

• 시간복잡도: O(log N), 매우 빠름!
• 활용 분야: 분수의 덧셈, 최소공배수 계산, 모듈러 연산

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

---

2. 소수 판별 (Primality Test)

주어진 수가 소수인지 판별하는 알고리즘

1) 기본적인 소수 판별 (O(√N))

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

✔ 활용: 암호학(RSA), 소수 찾기 문제

2) 에라토스테네스의 체 (O(N log log N))

1부터 N까지의 모든 소수를 빠르게 찾는 방법

def sieve(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return [i for i in range(n + 1) if primes[i]]

✔ 활용: 소수 개수 찾기, 소수 기반 문제

---

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

정수 계수 x, y를 구하는 방법 (Ax + By = GCD(A, B))

• 모듈러 역원(modular inverse) 계산에 활용

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

✔ 활용: RSA 암호 복호화, 정수 계수 조합 문제

---

4. 모듈러 연산 (Modular Arithmetic)

큰 수의 연산을 최적화할 때 사용!

• 활용: 암호학, 큰 수 계산

1) 거듭제곱의 모듈러 (O(log N))

def mod_pow(base, exp, mod):
    result = 1
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp //= 2
    return result

✔ 활용: RSA 암호 알고리즘, 수학 문제 최적화

---

5. 중국인의 나머지 정리 (Chinese Remainder Theorem, CRT)

여러 개의 모듈러 방정식을 풀 때 사용

예) x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

하나의 x 값으로 변환 가능

• 활용: 암호학(RSA), 시스템 해석 문제

---

6. 페르마의 소정리 (Fermat's Little Theorem)

p가 소수일 때, a^(p-1) ≡ 1 (mod p)

• 모듈러 역원 계산에 활용
• 확장된 RSA 알고리즘에서 중요

def mod_inverse(a, p):
    return pow(a, p - 2, p)  # a^(p-2) % p

---

7. 오일러 피 함수 (Euler's Totient Function)

1부터 N까지 N과 서로소인 수의 개수

✔ RSA 암호 체계에서 공개키 계산에 활용

✔ 수론적 문제 최적화 가능

def phi(n):
    result = n
    for p in range(2, int(n**0.5) + 1):
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
    if n > 1:
        result -= result // n
    return result

---

정리: 알고리즘 문제에서 유용한 정수론 개념

개념	설명	활용
유클리드 호제법	GCD & LCM 계산	분수 계산, 모듈러 연산
소수 판별	소수 찾기	암호학, 소수 기반 문제
확장 유클리드 알고리즘	Ax + By = GCD(A, B) 해 구하기	모듈러 역원 계산
모듈러 연산	큰 수 연산 최적화	암호학, 수학 문제
중국인의 나머지 정리 (CRT)	여러 모듈러 방정식 해결	RSA 암호 알고리즘
페르마의 소정리	모듈러 역원 계산	RSA 암호
오일러 피 함수	서로소 개수 구하기	암호학, 수론 문제