티스토리 뷰
목차
컴퓨터 과학과 암호학의 뿌리를 거슬러 올라가면 고대 그리스의 수학자 유클리드를 만나게 됩니다. 그가 고안한 유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD)를 구하는 가장 인류학적이고도 효율적인 방법입니다. 단순히 숫자를 일일이 나누어보는 방식을 넘어, 나머지를 이용한 순환 구조를 통해 아무리 거대한 숫자라도 순식간에 처리해내는 이 알고리즘은 현대 RSA 암호 시스템의 근간이 됩니다. 본 포스팅에서는 유클리드 호제법의 수학적 증명과 이를 응용한 최소공배수(LCM) 계산법을 2,500자 이상의 상세한 해설로 정리해 보겠습니다.
1. 유클리드 호제법의 정의와 호제(互除)의 논리
유클리드 호제법의 핵심은 "두 수 $a, b(a > b)$의 최대공약수는 $b$와 $a$를 $b$로 나눈 나머지($r$)의 최대공약수와 같다"는 성질에 있습니다. 이 과정을 나머지가 0이 될 때까지 반복하면, 마지막에 나누는 수로 쓰인 값이 바로 우리가 찾던 최대공약수가 됩니다. 예를 들어 GCD(192, 72)를 구한다면, 192를 72로 나눈 나머지 48을 이용해 GCD(72, 48)을 구하고, 다시 72를 48로 나눈 나머지 24를 이용해 GCD(48, 24)를 구합니다. 48은 24로 나누어떨어지므로 GCD는 24가 됩니다.
1-1. 뺄셈보다 나눗셈이 빠른 이유
과거에는 큰 수에서 작은 수를 계속 빼는 방식을 썼지만, 이는 두 수의 차이가 매우 클 때 연산 횟수가 지나치게 많아집니다. 나눗셈의 나머지($\%$) 연산을 이용하면 숫자의 크기가 로그 스케일로 급격히 줄어들기 때문에, 수천 자리에 달하는 거대 정수도 단 몇 밀리초 내에 계산이 완료됩니다. 이는 시간 복잡도 $O(\log(\min(a, b)))$를 보장하는 비결입니다.
2. 최소공배수(LCM)와 최대공약수의 유기적 관계
최대공약수를 알면 최소공배수(Least Common Multiple, LCM)는 산술적으로 즉시 도출됩니다. 두 수 $a, b$의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다는 수학적 원리를 이용합니다. 즉, LCM(a, b) = (a * b) / GCD(a, b)라는 공식이 성립합니다.
2-1. 구현 시의 주의사항: 오버플로우(Overflow) 방지
실무적으로 (a * b) / GCD 순서로 계산하면, 두 수의 곱셈 과정에서 정수형 범위를 넘어서는 오버플로우가 발생할 위험이 있습니다. 따라서 (a / GCD) * b 순서로 나누기를 먼저 수행하여 숫자의 크기를 조절한 뒤 곱셈을 진행하는 것이 프로그래밍적으로 훨씬 안전한 설계입니다.
3. 유클리드 호제법의 현대적 응용: 암호학
이 알고리즘은 단순히 수학 문제를 푸는 도구가 아닙니다. 현대 인터넷 보안의 핵심인 RSA 공개키 암호 알고리즘에서 두 소수의 곱과 서로소인 수를 찾기 위해 필수적으로 사용됩니다. 또한, 확장 유클리드 알고리즘(Extended Euclidean Algorithm)으로 발전하면 모듈러 연산의 역원을 구하는 등 고난도 보안 시스템의 수치 계산에 핵심적인 역할을 수행하게 됩니다.
구현 방식 비교: 재귀 vs 반복문
재귀 방식은 코드가 우아하고 수학적 정의를 그대로 반영하지만, 함수 호출 오버헤드가 발생할 수 있습니다. 반복문 방식은 성능상 미세하게 더 유리하고 안정적입니다. 두 방식 모두 로그 복잡도를 가지므로 대용량 데이터 처리에는 무리가 없으나, 시스템의 안정성을 고려한다면 반복문을 권장합니다.
# 유클리드 호제법 표준 구현 (Python)
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
# 오버플로우 방지를 위해 나누기 먼저 수행
return (a // gcd(a, b)) * b
1. 원리: 나머지를 이용해 숫자를 줄여나가며 공통된 최대 약수를 찾는 기법입니다.
2. 성능: 로그 시간 복잡도를 가져 대규모 데이터와 거대 정수 연산에 최적화되어 있습니다.
3. 활용: 암호화 키 생성, 분수 최적화, 주기성 파악 등 전산 수학의 기초가 됩니다.