C 언어로 구현하는 확장 유클리드 호제법(Extended Euclidean Algorithm)

확장 유클리드 알고리즘이란?

확장 유클리드 호제법(Extended Euclidean Algorithm)은 전통적인 유클리드 호제법을 확장한 알고리즘입니다. 단순히 두 정수 a와 b의 최대공약수(GCD)만 구하는 것이 아니라, 다음과 같은 베주 항등식(Bézout's identity)을 만족하는 정수 계수 x와 y까지 함께 찾아줍니다.

ax + by = gcd(a, b)

이 알고리즘은 재귀 호출을 통해 gcd(a, b)를 gcd(b mod a, a) 형태로 갱신해 나가며, 각 단계에서 얻은 계수 값을 거꾸로 추적하여 최종 결과를 계산합니다.

알고리즘

EuclideanExtended(a, b, x, y)

begin
    if a is 0, then
        x := 0
        y := 1
        return b
    end if
    gcd := EuclideanExtended(b mod a, a, x1, y1)
    x := y1 – (b/a)*x1
    y := x1
    return gcd
end

동작 원리를 단계별로 살펴보면 다음과 같습니다.

• a가 0이면 최대공약수는 b이며, 기본 해는 x = 0, y = 1입니다.
• 그렇지 않으면 (b mod a, a)에 대해 재귀적으로 함수를 호출하여 중간 결과 x1, y1을 얻습니다.
• x는 y1 − (b/a)·x1로, y는 x1로 갱신한 뒤 최대공약수를 반환합니다.

C 언어 구현 예제

#include <stdio.h>

int EuclideanExtended(int a, int b, int* x, int* y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int xtemp, ytemp; // 재귀 호출 결과를 저장할 변수
    int res = EuclideanExtended(b % a, a, &xtemp, &ytemp);
    *x = ytemp - (b / a) * xtemp;
    *y = xtemp;
    return res;
}

int main() {
    int x, y;
    int a = 60, b = 25;
    int res = EuclideanExtended(a, b, &x, &y);
    printf("gcd(%d, %d) = %d", a, b, res);
    return 0;
}

실행 결과

gcd(60, 25) = 5

결과 검증

a = 60, b = 25일 때 이 프로그램은 최대공약수가 5임과 동시에 x = -2, y = 5를 계산합니다. 실제로 대입해 확인하면 다음과 같습니다.

60 × (-2) + 25 × 5 = -120 + 125 = 5 = gcd(60, 25)

확장 유클리드 알고리즘의 활용 분야

확장 유클리드 알고리즘은 단순한 GCD 계산을 넘어 다양한 분야에서 핵심적인 역할을 합니다.

• 모듈러 역원 계산: mod m에서 a의 곱셈 역원을 구하는 데 사용되며, RSA를 비롯한 공개키 암호 알고리즘의 핵심 연산입니다.
• 선형 디오판토스 방정식: ax + by = c 형태의 방정식에 정수해가 존재하는지 판정하고 해를 구하는 데 활용됩니다.
• 중국인의 나머지 정리(CRT): 연립 합동 방정식을 풀 때 필수적인 도구로 사용됩니다.