핵심 인사이트

  1. 유클리드 호제법(Euclidean Algorithm)은 "두 수의 최대공약수(GCD)는 큰 수를 작은 수로 나눈 나머지와 작은 수의 GCD와 같다"는 원리 — 기원전 300년경 유클리드가 제안한 가장 오래된 알고리즘 중 하나로, GCD(a, b) = GCD(b, a mod b)로 표현된다.
  2. 시간 복잡도 O(log min(a, b)) — 피보나치 수열이 유클리드 호제법의 최악 케이스임이 수학적으로 증명되었으며, 심지어 10억 단위 수도 수십 번의 연산으로 GCD를 구할 수 있다.
  3. 유클리드 호제법의 확장(Extended Euclidean Algorithm)은 암호학의 기반 — 모듈러 역원(Modular Inverse) 계산에 사용되어 RSA 암호화, 중국인의 나머지 정리(CRT) 구현에 필수적이다.

Ⅰ. 알고리즘 원리

GCD (Greatest Common Divisor, 최대공약수):

두 수 a, b의 최대공약수 GCD(a, b):
  a와 b를 동시에 나누는 가장 큰 정수

예: GCD(48, 18)
  약수 48: {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}
  약수 18: {1, 2, 3, 6, 9, 18}
  공약수: {1, 2, 3, 6}
  최대공약수: 6

유클리드 호제법 핵심 원리:
  GCD(a, b) = GCD(b, a mod b)
  
  GCD(48, 18) 계산:
  단계 1: GCD(48, 18) = GCD(18, 48 mod 18) = GCD(18, 12)
  단계 2: GCD(18, 12) = GCD(12, 18 mod 12) = GCD(12, 6)
  단계 3: GCD(12, 6) = GCD(6, 12 mod 6) = GCD(6, 0)
  단계 4: b = 0 → a가 GCD → GCD = 6 ✓

왜 작동하는가?
  d가 a와 b 둘 다 나누면 → d는 (a - kb)도 나눔
  즉, d가 a와 b의 공약수이면 → a mod b의 약수이기도 함
  역도 성립 → GCD(a, b) = GCD(b, a mod b)

📢 섹션 요약 비유: 유클리드 호제법은 토지 측량 — 48m×18m 직사각형 땅을 정사각형으로 나눌 때 가장 큰 정사각형 크기가 GCD. "나머지로 다시 측량" 반복 = 유클리드!

Ⅱ. 구현

# 재귀 구현
def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

# 반복 구현 (스택 오버플로우 없음)
def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 테스트
print(gcd_iterative(48, 18))   # 6
print(gcd_iterative(100, 75))  # 25
print(gcd_iterative(13, 7))    # 1 (서로소)

# LCM (최소공배수) = a * b / GCD(a, b)
def lcm(a, b):
    return a * b // gcd_iterative(a, b)

print(lcm(4, 6))  # 12

# 시간 복잡도 증명 (피보나치 최악):
# GCD(F_{n+1}, F_n) = GCD(F_n, F_{n-1}) = ... = GCD(2, 1) = 1
# n번 연산 → O(log φ × min(a,b)) ≈ O(log min(a,b))

연산 횟수 비교:

GCD(1000000, 999999):
  유클리드: ~25번
  소인수분해 방법: 매우 오래 걸림
  
GCD(F_20, F_19) = GCD(6765, 4181):
  단계 1: GCD(6765, 4181)
  단계 2: GCD(4181, 2584)
  ...
  단계 19: GCD(2, 1)
  단계 20: GCD(1, 0) = 1
  → 피보나치 = 최악 케이스 (정확히 n-1번)

📢 섹션 요약 비유: 유클리드 알고리즘 구현 — while b != 0: a, b = b, a%b. 딱 한 줄이 수천 년 된 알고리즘. 피보나치 수 사이가 최악이지만 여전히 O(log n)!

Ⅲ. 확장 유클리드 호제법

확장 유클리드 호제법 (Extended Euclidean Algorithm)은 GCD(a, b) = ax + by를 만족하는 정수 x, y를 찾는 절차다. 이는 베주 항등식 (Bezout's Identity)을 계산 가능한 형태로 바꾼 것이며, 모듈러 역원과 RSA (Rivest-Shamir-Adleman) 개인키 계산에 직접 연결된다.

  • 목적: GCD(a, b) = ax + by를 만족하는 정수 x, y 찾기
  • 예시: GCD(48, 18) = 6, 48x + 18y = 6, 해는 x = -1, y = 3
  • 역추적:
    • 단계 1: 6 = 12 - 6×1
    • 단계 2: 6 = 12 - 1×(18 - 12×1) = 2×12 - 18
    • 단계 3: 6 = 2×(48 - 18×2) - 18 = 2×48 - 5×18

구현 예시는 다음과 같다.

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

# 모듈러 역원: a의 mod n 역원
# ax ≡ 1 (mod n) → GCD(a, n) = 1이면 역원 존재
def mod_inverse(a, n):
    gcd, x, _ = extended_gcd(a, n)
    if gcd != 1:
        return None  # 역원 없음
    return x % n

# RSA 예시: e의 φ(n)에 대한 역원 = d (복호화 키)
e, phi_n = 17, 3120
d = mod_inverse(e, phi_n)
print(d)  # 2753 (RSA 개인키 d 계산)

활용: RSA 암호: e×d ≡ 1 (mod φ(n))에서 d 계산 중국인의 나머지 정리: 연립 합동식 해 분수의 분모 유리화 (정수론)

📢 섹션 요약 비유: 확장 유클리드 = 암호 열쇠 제조 — GCD 계산하면서 동시에 RSA 개인키(d) 계산. 고대 수학이 현대 인터넷 보안(HTTPS)의 기반!

Ⅳ. 응용 문제

1. 분수 약분:
  48/18 = 48/GCD(48,18) / 18/GCD(48,18) = 8/3

2. 여러 수의 GCD:
  GCD(a, b, c) = GCD(GCD(a, b), c)
  
  GCD(12, 18, 24):
  GCD(12, 18) = 6
  GCD(6, 24) = 6

3. 배열의 GCD (Python):
  from math import gcd
  from functools import reduce
  nums = [12, 18, 24, 48]
  result = reduce(gcd, nums)  # 6

4. 타일링 문제:
  m×n 방을 a×a 정사각형 타일로 채울 때
  가장 큰 a = GCD(m, n)

5. 코딩테스트 패턴:
  "두 수의 공약수 개수" → 1~GCD(a,b) 범위에서 탐색
  "주기 최소화" → LCM 활용
  "톱니바퀴 회전" → LCM
  
6. 복잡도 비교:
  소인수분해 GCD: O(√max(a,b))
  유클리드 GCD: O(log min(a,b))
  
  1,000,000 입력:
  소인수분해: ~1,000번
  유클리드: ~20번 → 50배 빠름

📢 섹션 요약 비유: 유클리드 응용 — 타일 크기(공약수), 공통 주기(공배수), 암호 키 생성(모듈러 역원)까지. 고등학교 GCD가 프로그래밍 면접, 암호학, 게임 로직에 모두 등장!

Ⅴ. 실무 시나리오 — 스케줄링과 암호화

시나리오 1: 작업 스케줄링 (LCM)
  작업 A: 4분마다 실행
  작업 B: 6분마다 실행
  작업 C: 10분마다 실행
  
  세 작업이 동시 실행되는 주기:
  LCM(4, 6) = 12
  LCM(12, 10) = 60분
  → 1시간마다 동시 실행
  
  응용: 정기 배치 작업 충돌 예방
  LCM이 너무 크면 → 스케줄 분산

시나리오 2: RSA 키 생성 (Extended GCD)
  1. 두 소수 선택: p=61, q=53
  2. n = p×q = 3233
  3. φ(n) = (p-1)(q-1) = 3120
  4. e = 17 (GCD(17, 3120) = 1 확인)
  5. d = mod_inverse(17, 3120) = 2753
  
  공개키: (17, 3233)
  개인키: (2753, 3233)
  
  메시지 65 암호화: 65^17 mod 3233 = 2790
  복호화: 2790^2753 mod 3233 = 65 ✓

시나리오 3: 게임 파티클 동기화
  30 FPS 물리 엔진 + 60 FPS 렌더러
  GCD(30, 60) = 30
  LCM(30, 60) = 60 → 매 1/60초마다 동기화 가능
  물리: 매 2프레임(1/30초) 업데이트
  렌더: 매 프레임(1/60초) 렌더링

📢 섹션 요약 비유: 실무 유클리드 — 배치 작업 충돌 방지(LCM), RSA 암호키 생성(Extended GCD), 게임 프레임 동기화(GCD). 고대 수학이 현대 소프트웨어 어디에나!

📌 관련 개념 맵

유클리드 호제법
+-- 기본: GCD(a, b) = GCD(b, a mod b)
+-- 확장: ax + by = GCD(a, b)
|   +-- 모듈러 역원
|   +-- RSA 키 생성
+-- 파생
|   +-- LCM = a×b / GCD(a,b)
|   +-- 서로소 (GCD = 1)
+-- 복잡도: O(log min(a,b))
+-- 최악 케이스: 피보나치 수

📈 관련 키워드 및 발전 흐름도

[유클리드 원론 (기원전 300년)]
기하학적 GCD 증명
호제법 최초 기술
      |
      v
[베주의 정리 (1779)]
ax + by = GCD(a,b)
확장 유클리드 이론적 기반
      |
      v
[RSA 암호화 (1977)]
Extended GCD로 개인키 계산
현대 암호학 기반
      |
      v
[바이너리 GCD 알고리즘]
비트 연산 최적화
현대 CPU 최적화
      |
      v
[현재: 양자 컴퓨팅 위협]
쇼어 알고리즘: RSA 해독 가능
Post-Quantum 암호 연구

👶 어린이를 위한 3줄 비유 설명

  1. 유클리드 호제법은 땅 측량 — 48m×18m 땅을 정사각형으로 채울 때 가장 큰 정사각형 크기 찾기. 나머지로 반복하면 답!
  2. 확장 유클리드는 암호 열쇠 — GCD 계산하면서 동시에 RSA 개인키를 계산. 고대 수학이 인터넷 보안의 기반!
  3. LCM은 버스 출발 — 4분 간격 A, 6분 간격 B 버스가 동시 출발하는 주기 = LCM(4,6) = 12분. 스케줄 계산에 활용!