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

최대공약수(GCD)는 주어진 정수들을 모두 나누어떨어지게 하는 가장 큰 양의 정수입니다. 예를 들어, 8과 12의 최대공약수는 4이며 gcd(8, 12) = 4로 씁니다. 두 정수의 최대공약수가 1이면 두 수를 서로소라고 합니다.

예시: 상품 포장

올리브 오일 8병과 수제 비누 12개를 가지고 있다고 가정해 보겠습니다. 각 바구니에 품목별로 같은 수량을 넣어 선물 바구니를 만들려고 합니다. GCD는 만들 수 있는 최대 바구니 수를 파악하는 데 도움이 됩니다.

• 8의 약수는 다음과 같습니다: 1, 2, 4, 8
• 12의 약수는 다음과 같습니다: 1, 2, 3, 4, 6, 12

두 목록에 공통으로 있는 수 가운데 가장 큰 수는 4이므로 8과 12의 GCD는 4입니다. 이는 4개의 선물 바구니를 만들 수 있으며, 각 바구니에는 올리브 오일 2병(8 / 4 = 2)과 비누 3개(12 / 4 = 3)가 들어있다는 의미입니다.

계산 방법: 유클리드 호제법

약수를 모두 나열하는 방법은 작은 수에만 쓸 수 있습니다. 실제로는 유클리드 호제법을 씁니다. a를 b로 나눈 나머지를 r이라 하면 gcd(a, b) = gcd(b, r)이 성립하므로, 나머지가 0이 될 때까지 나눗셈을 반복하면 마지막으로 0이 아닌 나머지가 최대공약수입니다. 예를 들어 gcd(12, 8) = gcd(8, 4) = gcd(4, 0) = 4입니다. 반복 횟수는 수의 자릿수에 비례하는 정도에 그치므로, 수백 자리에 이르는 큰 수의 최대공약수도 컴퓨터로 매우 빠르게 계산할 수 있습니다.

확장 유클리드 호제법은 최대공약수와 함께 ax + by = gcd(a, b)를 만족하는 정수 x, y를 구합니다. gcd(a, n) = 1이면 이 계산으로 a의 모듈러 역원(a·x ≡ 1 mod n)을 얻을 수 있습니다.

암호학에서 GCD의 쓰임

• 서로소 확인: RSA에서 공개 지수 e는 φ(n)과 서로소여야 합니다(gcd(e, φ(n)) = 1). 이 조건을 GCD로 확인합니다.
• 모듈러 역원 계산: RSA의 개인 지수 d는 e의 모듈러 역원(e·d ≡ 1 mod φ(n))이며, 확장 유클리드 호제법으로 계산합니다. 여러 공개키 암호와 타원곡선 연산에서도 모듈러 역원이 쓰입니다.
• 공통 인수 공격: 난수 생성이 부실하여 서로 다른 두 RSA 키의 모듈러스가 같은 소인수를 공유하면, 두 모듈러스의 GCD를 계산하는 것만으로 그 소인수가 드러나 두 개인 키가 모두 노출됩니다. 많은 공개키를 한꺼번에 검사하는 배치 GCD(batch GCD) 방법으로 실제 인터넷에서 수집한 키 가운데 이런 취약한 키가 발견된 사례가 있습니다.

GCD가 유용한 이유

GCD는 분수를 약분하고, 톱니바퀴와 비율 문제를 풀며, 암호 알고리즘의 키 생성과 검증에도 쓰입니다. 실생활과 암호학에 널리 응용되는 수학의 기본 개념입니다.