[정수론] 떠먹여주는 유클리드/확장 유클리드 알고리즘

안녕하세요, 전도연입니다.

 

유클리드 알고리즘과 확장 유클리드 알고리즘은 처음 공부하면 이해가 어렵기도 합니다.

그럴 때에는 수학적 관계를 중점적으로 살펴보면 이해에 도움이 됩니다.

본문에서 자세히 다룰 터이니 이해에 도움이 되었으면 좋겠습니다.

 

1. Euclidean Algorithm

---

유클리드 알고리즘 (유클리드 호제법)은 두 수의 최대공약수를 빠르게 찾는 알고리즘으로, 다음과 같은 두 가지 사실에 기반을 둡니다.

1. $gcd(a, b) == gcd(b, r)$ ($r = a\: mod \: b$, $a > b > 0$인 정수)
2. $gcd(a, 0) = a$

$gcd(a, b) = gcd(b, a \mod b)$ 증명

---

귀류법을 사용해 1의 식이 참이 됨을 증명하겠습니다.

[Proof]
gcd(a, b) == gcd(b, r) (r = a%b, a > b > 0)

g  = gcd(a, b)
g' = gcd(b, r)

1. Assume that g > g' > 0
(1) r  = a - kb (k는 정수)
a, b는 모두 g의 배수이므로 이를 사용해 나타내면
(2) r = g * (a/g) - k * g * (b/g)
(3) r = g ( a/g - k * (b/g) )
따라서 r은 g의 배수이다.
(4) r, b는 모두 g의 배수이고, gcd(r, b) = g' 이므로 g' >= g 임이 성립.
(5) 이는 가정에 모순.

2. Assume that g' > g > 0
(1) a = k*b + r
b, r은 모두 g'의 배수이므로 이를 사용해 나타내면
(2) a = k * g' * (b/g') + g' * (r/g')
(3) a = g' * (k * (b/g') + (r/g'))
따라서 a는 g'의 배수이다.
(4) a, b는 모두 g'의 배수이고, gcd(a, b) = g 이므로 g >= g' 임이 성립.
(4) 이는 가정에 모순.

따라서 g = g' 임이 증명되었다.

gcd() 함수의 두 번째 인자가 0이 될 때까지 재귀적으로 호출하면 되는데, 두 번째 인자가 0일 때의 첫 번째 인자가 처음 두 수의 최대공약수입니다.

 

예시를 좀 들어보겠습니다.

40과 32의 최대 공약수를 구하는 gcd(40, 32)의 경우를 통해서요.

 

1. gcd(40, 32) 호출

2. gcd(32, 40%32) == gcd(32, 8) 호출

3. gcd(8, 32%8) == gcd(8, 0) 호출. 두 번째 인자가 0이므로 첫 번째 인자인 8이 최대공약수가 됩니다.

 

이렇게 예시를 들어 이해하면 정말 쉽습니다.

구현은 재귀 함수를 사용하거나 반복문을 사용할 수 있습니다.

 

재귀 함수로 Euclidean Algorithm 구현하기

---

def gcd(a, b):
	if(b == 0):
		return a
	else:
		return gcd(b, a%b)

while 문으로 Euclidean Algorithm 구현하기

---

def gcd(a, b):
	while b != 0:
    		a, b = b, a % b
    return a

 

티스토리 indent가 좀 이상한 것 같은데 양해 바랍니다.

 

2. Extended Euclidean Algorithm (xgcd)

---

확장 유클리드 알고리즘을 사용하면 베주 항등식 $ax+by=gcd(a, b)$ 를 만족하는 $x$, $y$를 구할 수 있습니다.

($gcd(a, b) = 1$ , 즉 $a$와 $b$가 서로소인 경우 이들의 modulo inverse 또한 xgcd를 통해 계산할 수 있습니다.)

xgcd는 gcd 계산 과정을 따라가면서도 이때 사용되는 값들을 추가적으로 기록함으로써 구현할 수 있습니다. 아, 식을 만족하는 $x$, $y$는 유일하지 않지만 이 글에서는 음수가 아닌 최소 정수로 한정하고 알고리즘을 작성합니다.

$gcd(a, b) = gcd(b, r) = g$ 라는 식을 통해 확장 유클리드 알고리즘의 각 단계에서 사용되는 변수 값 간의 관계를 살펴봅시다.

먼저 $r$을 $a, b$에 대해 나타내면 다음과 같습니다.
$r =  a - bq$, ($q = a//b$)

따라서 $gcd(b, r) = b*x_1 + r*y_1$ 이라는 베주 항등식은 아래의 식으로 정리됩니다.
$gcd(b, r) = b * x_1 + (a - bq) * y_1$

그 다음, $gcd(a, b)$를 $x_2$와 $y_2$라는 변수를 사용해 베주 항등식 형태로 나타낼 수 있습니다.
$gcd(a, b) = a * x_2 + b * y_2$

이때 $gcd(a, b) = gcd(b, r)$ 이므로 두 식을 등호로 묶어 정리하는 것이 가능합니다.
$a * x_2 + b * y_2 = b * x_1 + (a - bq) * y_1$
적절히 $a$, $b$로 묶어 정리한 식은 아래와 같습니다.
$a * x_2 + b*y_2 = a * y_1 + b (x_1-q*y_1)$

따라서 $x_2 = y_1$이고, $y_2 = (x_1 - q * y_1)$임을 알 수 있습니다.

xgcd는 gcd의 재귀 호출 흐름을 거슬러 올라가며 진행됩니다.
gcd의 호출 흐름이 $gcd(5, 2) -> gcd(2, 1) -> gcd(1, 0)$ 과 같은 식이라면, xgcd가 베주 항등식을 만족하는 값을 구할 때 사용하는 식은 $gcd(1, 0) -> gcd(2, 1) -> gcd(2, 5)$ 이런 순서인 것입니다. 너무 당연한 이야기지만 $gcd(5, 2)$에서 바로 $x$, $y$ 값을 계산해낼 수 있었으면 이 고생을 하지 않았을 겁니다.

우리가 방금 예시를 든 $gcd(a, b) = gcd(b, r)$의 경우를 따져보자면, $gcd(b, r)$로부터 $x_1$, $y_1$을 먼저 구해낸 뒤 $gcd(a, b)$에서 $x_2$, $y_2$를 구해내는 것이 올바른 순서입니다. 이때 이전 단계 ($gcd(b, r)$)에서 구한 $y$ 값은 다음 단계 ($gcd(a, b)$)의 $x$ 값으로 쓰이는 것을 알 수 있습니다. 이런 연쇄적 특성을 이용해 gcd의 흐름을 거슬러 올라가며 최종적인 $x$, $y$ 값을 구하는 것이 xgcd 알고리즘입니다.

계산 과정을 예로 들어 살펴보면 이해가 더욱 쉬울 겁니다.

 

Example. $xgcd(5, 17)$

---

$xgcd(5, 17)$로 $5x + 17y = gcd(5, 17) = 1$의 식을 만족하는 $x$, $y$ 값을 구하는 과정을 살펴봅시다.
$gcd(5, 17)$을 재귀적으로 계산한다면 호출 흐름은 아래와 같습니다.

$gcd(5, 17)$ -> $gcd(17, 5)$ -> $gcd(5, 2)$ -> $gcd(2, 1)$ -> $gcd(1, 0)$ -> yield $1$

$gcd(1, 0)$부터 흐름을 거슬러 올라가면서 $gcd(a, b) = ax + by$ 형식의 베주 항등식을 작성해봅시다.

$gcd(1, 0) = 1 = 1*x_1 + 0*y_1$
이때 $x_1$는 1이어야 하고, $y_1$은 아무 값이나 들어와도 만족하지만 음수가 아닌 최소 정수를 구할 것이므로 $y_1$은 0입니다.
따라서, $1 = 1 * 1 + 0 * 0$ 이 올바른 베주 항등식입니다.

$gcd(2, 1) = 1 = 2*x_2 + 1*y_2$
이때 $x_2$는 이전 계산에서 구한 $y_1$이어야 합니다. 따라서 $x_2 = 0$이고, $y_2 = 1$입니다.

$gcd(5, 2) = 1 = 5*x_3 + 2*y_3$
$x_3 = 1$이므로 $y_3 = (1 - 5*x_3)/2 = (1-5*y_2)/2 = -2$ 입니다.

$gcd(17, 5) = 1 = 17*x_4 + 5*y_4$
$x_4 = -2$이므로 $y_4$ 역시 간단하게 계산할 수 있습니다. $y_4 = (1 - 17*x_4)/5 = (1 - 17*y_3)/5 = 7$

$gcd(5, 17) = 1 = 5*x_5 + 17*y_5$
$x_5 = y_4$, $y_5 = -2$ 입니다.

이로써 $xgcd(5, 17)$의 결과를 다음과 같이 정리할 수 있습니다.
$1 = 5*7 + 17*(-2)$

 

재귀 함수로 Extended Euclidean Algorithm 구현하기

---

xgcd()를 구현한 코드는 아래와 같습니다.

def xgcd(a, b):
	if(b == 0):
		# 최종 단계 gcd(a, 0) = a*1 + 0*0 이므로.
		return (a, 1, 0)
	else:
		g, x1, y1 = xgcd(b, a%b)  
		# 이전 단계의 계산 결과를 g(최대공약수), x1 (이전 단계의 x값), y1(" y값) 에 저장
		x, y = y1, (g - a * y1)//b
		# 이전 단계의 결과를 바탕으로 이번 단계의 x, y 값을 구성한 뒤 반환
		return (g, x, y)

생각보다 정말 간단하지 않나요

그럼 건승을 빕니다