확장 유클리드 알고리즘과 모듈러 역원의 원리 및 활용

확장 유클리드 알고리즘은 기본적인 최대공약수(GCD) 계산을 넘어, 선형 디오판토스 방정식 \(ax + by = \gcd(a, b)\) 의 정수해를 구하는 데 사용된다. 이는 특히 모듈러 산술에서 역원을 구할 때 핵심적으로 활용되며, 암호학이나 수치 해석 분야에서 중요하게 다뤄진다.

기본 개념 및 작동 원리

유클리드 알고리즘은 두 정수 \(a\)와 \(b\)에 대해 \(\gcd(a, b) = \gcd(b, a \bmod b)\)라는 성질을 이용하여 재귀적으로 최대공약수를 구한다. 확장된 형태에서는 이 과정 중 각 단계의 계수 관계를 추적함으로써, 최종적으로 \(ax + by = d\) (\(d = \gcd(a,b)\))를 만족하는 정수쌍 \((x, y)\)를 찾아낸다.

기저 사례로, \(b = 0\)일 경우 \(\gcd(a, 0) = a\)이므로, 방정식은 \(a \cdot x + 0 \cdot y = a\)가 되고, 이때 \(x = 1\), \(y = 0\)이 자연스럽게 해가 된다. 이후 재귀 호출로부터 반환된 값들을 활용해 현재 단계의 해를 역추적한다.

재귀 호출 시점에서 이미 \(bx' + (a \bmod b)y' = d\)의 해 \((x', y')\)가 구해졌다고 가정하면, \(a \bmod b = a - \lfloor a/b \rfloor \cdot b\)임을 이용해 식을 전개할 수 있다:

\[ bx' + (a - \lfloor a/b \rfloor \cdot b)y' = ay' + b(x' - \lfloor a/b \rfloor y') = d \]

따라서 원래 식 \(ax + by = d\)와 비교하면 다음 관계를 얻는다:

\[ \begin{aligned} x &= y' \\ y &= x' - \left\lfloor \frac{a}{b} \right\rfloor y' \end{aligned} \]

코드 구현 방법

위의 관계를 기반으로, 참조 매개변수를 통해 값을 상향 전달하는 방식으로 구현할 수 있다. 아래는 가장 일반적인 형태의 C++ 스타일 구현이다:

int extended_gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int g = extended_gcd(b, a % b, y, x); // x, y의 역할을 교환
    y -= (a / b) * x;
    return g;
}

여기서 주목할 점은 재귀 호출 시 y와 x의 위치를 바꿔 전달하는 것이다. 이를 통해 다음 단계에서 얻은 \(x'\)와 \(y'\)가 현재 단계의 \(y\)와 \(x\)에 자동으로 대입되며, 갱신 로직이 간결해진다.

모듈러 역원 계산

모듈러 역원이란, \(a \cdot x \equiv 1 \pmod{m}\) 을 만족하는 \(x\)를 의미하며, 이는 \(ax + my = 1\) 형태의 방정식으로 전환할 수 있다. 이러한 해가 존재하기 위한 필요충분조건은 \(\gcd(a, m) = 1\), 즉 \(a\)와 \(m\)이 서로소라는 점이다.

예를 들어, \(a = 3\), \(m = 4\)인 경우, \(3x \equiv 1 \pmod{4}\)를 만족하는 \(x\)는 \(x = 3\)이며, 실제로 \(3 \times 3 = 9 \equiv 1 \pmod{4}\)이다. 또한 모든 해는 \(x + k \cdot (m/d)\) 꼴이므로, 무한히 많은 역원이 존재할 수 있다.

특히 \(m\)이 소수일 경우, 페르마의 소정리를 이용해 \(a^{-1} \equiv a^{m-2} \pmod{m}\)으로 역원을 빠르게 계산할 수 있으며, 이는 지수 연산을 빠른 거듭제곱법(fast exponentiation)으로 처리하면 효율적이다.

선형 방정식 해법 응용

확장 유클리드 알고리즘은 다음과 같은 문제 해결에 직접적으로 사용된다.

정수해 존재 여부 판단

방정식 \(ax + by = k\)가 정수해를 가지려면, 베주 항등식에 의해 \(\gcd(a, b) \mid k\)이어야 한다. 코드로는 다음과 같이 확인 가능하다:

int x, y;
int d = extended_gcd(a, b, x, y);
if (k % d != 0) {
    // 해 없음
} else {
    // 해 존재
}

특정 조건의 해 찾기

정수해가 존재하면, 일반해는 다음과 같다:

\[ x_k = x_0 + k \cdot \frac{b}{d}, \quad y_k = y_0 - k \cdot \frac{a}{d} \]

비음의 정수해: \(x \geq 0\), \(y \geq 0\)을 만족하도록 \(k\)를 조정한다.
양의 정수해: \(x > 0\), \(y > 0\)이 되도록 보정하며, \(x=0\) 또는 \(y=0\)인 경우 통해를 더해 조정한다.
해의 개수: 가능한 \(k\)의 범위를 계산하여 전체 해의 수를 결정한다.
최대/최소값: 통해를 더하거나 빼서 \(x\) 또는 \(y\)의 최댓값, 최솟값을 도출한다.

삼원 일차 방정식으로의 확장

세 변수에 대한 방정식 \(ax + by + cz = k\)도 확장 유클리드를 활용해 풀 수 있다. 먼저 \(g = \gcd(a, b)\)에 대해 \(ax + by = g\)의 해를 구한 후, \(g \cdot t + cz = k\) 형태로 축약하여 다시 확장 유클리드를 적용하면 된다. 이처럼 복잡한 문제도 두 변수씩 분해해 접근 가능하다.

실제 코딩 문제(P5656 등)에서도 비음의 해 개수, 경계값 계산 등이 요구되며, 위의 논리를 체계적으로 구현하는 것이 중요하다.

태그: 확장 유큌리드 모듈러 역원 디오판토스 방정식 페르마의 소정리 빠른 거듭제곱

6월 17일 22:32에 게시됨

괴물 클럽