C++로 구현하는 확장 유클리드 호제법(Extended Euclidean Algorithm) 프로그램

확장 유클리드 호제법(Extended Euclidean Algorithm)은 두 수의 최대공약수(GCD)를 구하는 또 다른 방법입니다. 일반적인 유클리드 호제법과 달리, ax + by = gcd(a, b)라는 베주 항등식(Bézout's identity)을 만족하는 정수 계수 x와 y까지 함께 계산하는 추가 변수를 사용합니다. 이러한 특성 덕분에 모듈로 역원을 구하거나 암호학 알고리즘을 구현할 때 특히 유용하며, 재귀적 구조로 작성하면 컴퓨터 프로그램에서도 효율적으로 동작합니다.

알고리즘

Begin
   변수 a, b, x, y 선언
   gcdExtended(int a, int b, int *x, int *y)
   if (a == 0)
      *x = 0;
      *y = 1;
   return b;
   결과를 저장할 두 개의 변수(x1, y1) 준비
   재귀 호출의 결과값을 이용해 x와 y 갱신
End

동작 원리:

• 재귀 호출이 a == 0에 도달하면 gcd(b, 0) = b가 되므로 기저 조건에서 b를 반환하고, *x = 0, *y = 1로 설정합니다.
• 재귀적으로 gcdExtended(b % a, a, &x1, &y1)를 호출해 하위 문제의 해를 구합니다.
• 반환된 값들을 이용해 *x = y1 - (b/a) * x1, *y = x1 공식으로 현재 단계의 계수를 갱신합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int gcdExtended(int a, int b, int *x, int *y) {
   if (a == 0) {
      *x = 0;
      *y = 1;
      return b;
   }
   int x1, y1;
   int gcd = gcdExtended(b%a, a, &x1, &y1);
   *x = y1 - (b/a) * x1;
   *y = x1;
   return gcd;
}
int main() {
   int x, y;
   int a = 35, b = 15;
   cout<<"gcd "<<gcdExtended(a, b, &x, &y);
   return 0;
}

실행 결과

gcd 5

위 코드는 a = 35, b = 15일 때 최대공약수 5를 출력합니다. 실제로 35 × (-1) + 15 × 2... 즉, 적절한 x와 y 조합을 통해 ax + by = gcd(a, b)가 성립함을 확인할 수 있으며, 함수에 포인터로 전달된 x, y 변수에는 해당 계수들이 저장됩니다.