확장 유클리드 호제법

확장 유클리드 호제법

 

기말 기간이라 밀렸던 문제 해결 기법 강의를 듣고 있는데 확장 유클리드 호제법이 나왔다.

 

유클리드 호제법을 알고 있었고 가끔씩은 백준 푸는 데 사용했었기 때문에 어렵지 않게 이해하고 넘어가야지 했는데

 

뭐지? 이해가 안가네? 

 

옛날 같았으면 그냥 에라이 모르겠다 하고 넘어갔을 텐데 뭔가 시험에 나올 것 같다는 강렬한 촉이 와서 정리해봤다.

(개인적인 이해를 바탕으로 작성했기 때문에 완벽하진 않아요!)

 

 

확장 유클리드 호제법을 이해하려면 먼저 유클리드 호제법을 이해해야 한다.

 

일명 GCD 알고리즘이라고도 불리며 "수학"이란 카테고리에서는 가장 처음 접하는 알고리즘 다운 알고리즘이다.

 

자세하게 설명하는 건 생략하고 요약하자면 

 

결국 유클리드 호제법을 간단히 말하면 "log 시간안에 최대공약수를 구하는 방법"이다.

 

유클리드 호제법 코드

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

 

가장 간단하면서 이해하기 쉬운 코드이다.

 

 

이제 유클리드 호제법을 확장시켜보자.

 

가장 먼저 베주 항등식에 대해 알아야 한다. 

알아야 한다기 보단.. 그냥 이런 게 있구나를 알아야 한다.

 

베주 항등식이란 두 정수의 최대공약수를 원래 두 수의 배수의 합으로 나타낼 수 있다는 정리다. (feat. wiki)

 

두 정수 a, b에 대하여 두 정수의 최대공약수, 즉 GCD(a, b)는 a를 x배 한 값과 b를 y배 한 값의 합으로 나타낼 수 있다는 것이다. (이때 x와 y 역시 정수)

 

이 말을 그대로 식으로 나타내보면

ax + by = GCD(a, b)이다.

 

이 식을 가지고 확장된 유클리드 호제법을 사용하면 x와 y를 구할 수 있다.

 

즉 확장된 유클리드 호제법은 주어진 a와 b를 통해 GCD(a, b) 뿐만 아니라 x, y까지 구해주는 알고리즘이다.

 

이제 확장 유클리드 호제법이 어떤 과정을 통해 GCD(a, b)와 x, y까지 구해주는지 천천히 살펴보자.

 

대부분의 블로그들은 표를 사용하여 설명하고 있다. 

솔직히 처음 표를 보면 이해하기 쉽지 않았다. 물론 내가 바보인 걸 수도 있지만..

혹시 표를 보며 이해가 되지 않는다면 내 설명이 도움이 되었으면 좋겠다

 

 

a = 38, b = 4라고 가정하자.

그럼 우리는 38x + 4y = GCD(38,4)라는 식을 얻을 수 있다.

 

여기서 유클리드 호제법에 의해 GCD(38,4)를 한 단계만 계산해보면 38 mod 4이다.

 

즉 38 mod 4 = 2이고 2는 38과 4의 공약수 중 하나이다. (유클리드 호제법에 의해 + 최대공약수인진 확신 못함)

 

그럼 38x + 4y = 2라는 식을 얻을 수 있다.

 

이를 표로 나타낸 것이 아래와 같다.

	x	y	c	GCD(a,b) 단계별 몫(q)
i = 0	1	0	38
i = 1	0	1	4	9
i = 2			38 mod 4 = 2

대부분의 블로그에서 이런 방식의 표를 보여주는데 이는 코드 구현 방식을 이해하기 쉽게 나타낸 것이다.

 

따라서 i = 0일 때와 i = 1일때는 말 그대로 초기화 과정이라고 생각하면 된다.

 

i = 0일때 x = 1이고 y = 0이라 초기화하면 c값은 당연히 38이다. (식 38*1 + 4*0 = 38에 의하여)

i = 1일 때도 마찬가지이다.

 

이제 i = 2일 때의 나머지 부분을 채워넣어야 한다.

 

i = 2일때의 c 값을 2라고 구했다. 그럼 c 값이 2가 되기 위한 x와 y값은 어떻게 구해야 할까?

 

답은 초등학교 때 배운 나머지 연산에 있다.

이게 왜 필요할까? 

 

현재 내가 얻은 식은 38x + 4y = 2란 식이고 x와 y를 구해야 한다.

 

이때 유클리드 호제법에 의해 반드시 a가 더 큰 수이므로 4와 38/4의 몫을 곱한 수는 어떠한 경우에도 a보다 작다.

따라서 y값이 -9라 한다면 x의 값은 38x = 2 - 4y, 즉 x = 1이 된다.

사람이 손으로 푼다면 이렇게 풀 것이다. 

 

근데 나는 앞에서 궁금한 점은 왜 i = 0과 i = 1을 초기화해야 했을까? 였다.

 

결론부터 말하면  X_i+2 = X_i-2 - Xi-1*q,  Y_i+2 = Y_i-2 - Yi-1*q 이기 때문이다.

 

왜 이 식이 성립하는지는 위에서 언급했던 과정들을 잘 생각해보면 당연하다.

(기계가 풀어야 하기 때문에 식으로 나타내면 위와 같아진다.)

 

결국 이런 과정을 통해서 얻게 되는 표는 아래와 같다.

	x	y	c	GCD(a,b) 단계별 몫(q)
i = 0	1	0	38
i = 1	0	1	4	9
i = 2	1	-9	38 mod 4 = 2
i = 3			0

c 값이 0이 됐다는 것은 GCD(a, b) = 0이 되었다는 뜻이므로 종료하고 이전의 값이 최대 공약수가 된다.

 

따라서 c가 최대 공약수일 때 x와 y의 값은 1과 -9 임을 알 수 있다.

 

이제 a와 b만 알고 있다면 x, y GCD(a, b)를 빠르게 구할 수 있게 되었다.

 

(코드는 아래 블로그에서 잘 작성되어 있기 때문에 추천만 해드릴게요.. 직접 구현하는 일은... 없을 것 같네요^^)

https://www.crocus.co.kr/1232

 

 

나머지 연산(mod)의 곱셈의 역원 구하기

 

사실상 확장 유클리드 호제법을 공부한 이유가 나머지 연산의 곱셈의 역원을 구하기 위해서라고 해도 틀리지 않다.

 

내 경험담이긴 하지만 2020 Shake! (경인지역 6개 대학 알고리즘 경시대회) 예선전에서 이와 관련된 문제가 출제되었었다. 

 

그때는 이게 확장된 유클리드 호제법을 써야 되는지도 모르고 수식만 끄적이다 A4 5장을 꽉 채운 뒤 포기했었다....

 

 

본론으로 돌아가서 나머지 연산의 곱셈의 역원을 알아보자.

 

먼저 곱셈이 역원이란 그 수와 곱하면 1이 되는 수를 말한다.

 

이때 나머지 연산(mod)에서의 곱셈의 역원이란 두 수를 곱했을 때 나머지 연산을 통해 1의 값을 가지게 되면 된다는 것이다.

이는 식으로 나타내면 아래와 같다.

 

a * s ≡ 1 (mod p)

(단 반드시 a와 p는 서로 서로소여야 한다.)

 

이 부분에서 살짝 헤맸는데 예시가 가장 이해하기 좋다.

 

예를 들어 mod 11이라고 했을 때 5에 대한 나머지 연산의 곱셈의 역원은 9이다.

이유는 5*9 = 45이고 45%11 = 1이기 때문이다.

(이 부분이 이해가 안 된다면 꼭 "나머지 연산", "모듈러 연산"에 대해 찾아보길 바람)

 

아니 근데 이게 어떤 부분에서 확장 유클리드 호제법과 관련이 있을까?

 

빨간색은 괜히 있는 게 아니다.

 

위에서 언급했듯이 반드시 a와 p는 서로소여야 한다고 했다.

 

그리고 서로소인 두 수의 최대공약수는 1이다.

 

우리는 위에서 확장 유클리드 호제법을 공부했기 때문에 a*x + b*y = GCD(a, b) 임을 알고 있다.

 

그렇다면 a*x + p*y = GCD(a, p) = 1이라는 식을 도출하는 건 어렵지 않다.

 

따라서 우리는 x와 y값을 빠르게 구할 수 있다.

 

위의 사진은 실제 코드로 계산한 값이다.

 

그럼 이제 X = 1이고 Y = -2라는 것을 알았다.

 

이때 중요한 건 그럼 나머지 연산의 곱셈의 역원 값은 어떤 것인가?

 

잘 생각해보면 당연히 Y값인 걸 알 수 있겠죠?

 

결국 식 a * s ≡ 1 (mod p)에서 s를 구하기 위한 것이었으므로 Y값이 곱셉의 역원이 된다.

 

여기서 음순데 어쩌라고?라는 생각이 들었다면 아직 나머지 연산에 대한 이해가 부족한 것이다.

 

-2 (mod 11) = 9 (mod 11)과 같다.

 

이렇게 확장된 유클리드 호제법을 이해하고 있다면 어렵지 않게 구할 수 있다.