For a better world

확장 유클리드 알고리즘

$x, y$에 대한 부정방정식 $ax + by = c$는 $c$의 값이 $gcd(a,b)$의 배수일 때만 정수 해를 가진다 알려져있다. 즉, $ax + by = c$가 정수 해를 가지는 $c$의 최솟값이 $gcd(a,b)$가 되는 것이다. 따라서 확장 유클리드 알고리즘은 $a,b$의 최대공약수를 구하는 것에 더 나아가, $ax + by = gcd(a,b)$를 만족하는 정수 해 $x,y$도 구하는 알고리즘이라할 수 있다. 즉, 다음과 같다.

• 확장 유클리드 호제법을 이용하면 $ax + by = gcd(a,b)$의 해가 되는 정수 $x, y$ 짝을 찾아낼 수 있다. 특히 $a,b$가 서로소$(gcd(a,b)=1)$인 경우 유용한데, 이와 같을 경우 $ax + by = 1$이 되고, 여기서 a는 모듈러 연산의 곱의 역원이 되기 때문이다.

유클리드 확장 알고리즘 증명

유클리드 확장 알고리즘 증명에 앞서 먼저 유클리드 알고리즘은 다음과 같다.

두 양의 정수 a,b의 최대공약수 $gcd(a,b)$는 다음과 같은 절차를 거쳐 구할 수 있다.

$r_0 ← a$

$r_1 ← b$

$r_{i+1} = r_{i-1} - q_i r_i$

$q_i = r_{i-1} \div r_i$

만약 $r_{i+1} = 0$이라면, $r_i$가 바로 $gcd(a,b)$이다.

확장 유클리드 알고리즘의 경우 최대공약수 이외에도 다음을 만족하는 두 개의 정수 $s, t$를 추가로 구할 수 있다.

$sa + tb = gcd(a,b)$

초기 조건은 다음과 같다.

$s_1 = 1,\ s_2 = 0$

$t_1 = 0,\ t_2 = 1$

$r_1 = a,\ r_2 = b$

$as_i + bt_i = r_i\ \ for\ i = 0,1$

초기 조건을 대입하여 확인할 수 있으며, $i >$ 1일 때 참이라 가정하고 수학적 귀납법을 사용하면 다음과 같다.

$r_{i+1} = r_{i-1} -r_iq_i$

$= (as_{i-1} + bt_{i-1}) - (as_i+bt_i)q_i$

$= a(s_{i-1}-s_iq_i)+b(t_{i-1}-t_iq_i)$

$= as_{i+1}+bt_{i+1}$

따라서 $r_{i+1} = 0$일 때, $as_i + bt_i = r_i$는 $sa + tb = gcd(a,b)$가 된다.

모듈러 연산에서 곱셈에 대한 역원 구하기

법 $m$에 대한 모듈러 연산에서 정수 $a$의 곱셈에 대한 역원 $a^{-1}$은 다음을 만족하는 정수 $x$로 정의한다.

$ax \equiv 1\ (mod\ m)$

모듈러 연산의 정의에 의해 $ax - 1 = -my$를 만족하는 정수 $y$가 존재해야하며 이는 다시 말해 다음을 만족하는 정수$x, y$가 존재해야 한다는 의미이다.

$ax + my = 1$

$a$와 $m$의 최대공약수가 1, 즉 서로소이면 해가 존재하고 그렇지 않을 경우 $a^{-1}$은 존재하지 않는다.

그렇다면... (추가 기술 필요)

확장 유클리드 알고리즘 의사코드

#1

function extended_gcd(a, b)
    s <- 0;    old_s <- 1
    t <- 1;    old_t <- 0
    r <- b;    old_r <- a
    while r ≠ 0
        quotient <- old_r div r
        (old_r, r) <- (r, old_r - quotient * r)
        (old_s, s) <- (s, old_s - quotient * s)
        (old_t, t) <- (t, old_t - quotient * t)       
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

#2

// 초기화
r1 ← a, r2 ← b

s1 ← 1, s2 ← 0

t1 ← 0, t2 ← 1



// 루프
while(r2 > 0)
{
　q ← r1 / r2

　r ← r1 - q*r2
　r1 ← r2
　r2 ← r

　s ← s1 - q*s2
　s1 ← s2
　s2 ← s

　t ← t1 - q*t2
　t1 ← t2
　t2 ← t
}

Reference

[1] https://codepractice.tistory.com/79?category=885924

[2] https://brilliant.org/wiki/extended-euclidean-algorithm/

[3] https://ko.wikipedia.org/wiki/유클리드_호제법

[4] https://codeonwort.tistory.com/295

[5] https://joonas.tistory.com/25

[6] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm