확장 유클리드 알고리즘

 

 

---

목차

 

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

 

2. 확장 유클리드 알고리즘 동작원리

 

3. 확장 유클리드 알고리즘 소스 코드

 

4. 나머지 연산 곱셈 역수(역원) 구하기 

---

 

 

 

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

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95#.ED.98.B8.EC.A0.9C.EB.B2.95.EC.9D.98_.ED.99.95.EC.9E.A5

 

 

우선 유클리드 알고리즘에 대해 한번 알아보자.

 

https://youtu.be/J5Yl2kHPAY4

 

 

그리고 유클리드 알고리즘 코드를 확인해보자.

 

http://www.crocus.co.kr/1054

 

 

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

 

ax + by = c에서 c의 값이 gcd(a, b)의 배수일 때만 정수해를 갖는다고 알려져있다.

 

따라서 ax + by = c가 정수해를 갖는 c의 최솟값이 gcd(a,b)가 되는 것이다.

 

이를통해 확장 유클리드 알고리즘은 a, b의 최대 공약수와 ax + by = gcd(a,b)를 만족하는 x, y도 구하는 알고리즘이다.

 

 

 

 

2. 확장 유클리드 알고리즘 동작원리

 

이 부분은 http://joonas.tistory.com/25를 이용하여 작성하였습니다.

(문제의 소지가 있다면 삭제 조치 하겠습니다.)

 

 

a*s + b*t = gcd(a,b)를 만족하는 정수 s, t 짝을 찾아보고자 한다.

 

 

초기 설정은 위와같이 init처럼 해주고 확장 유클리드 알고리즘 과정은 progress부분처럼 진행된다.

 

이제 어떻게 진행되는지 표를 한번 작성해보자.

 

26s + 8t = 2( == gcd(26,8))를 만족하는 값을 구해보자.

 

초기 표 설정은 아래와 같이한다.

	Si	Ti	Ri	Qi
i = 0	1	0	a
i = 1	0	1	b	⌊ a / b ⌋
			a mod b

 

그다음 위의 예제를 이용하여 한번 넣어보자.

 

	Si	Ti	Ri	Qi
i = 0	1	0	26
i = 1	0	1	8	3 (26 / 8)
i = 2			2 (26 mod 8)

 

 

우리는 Ri가 0이 되는 순간 모든 과정을 끝낼 것인데 아직 Ri가 0이 되지 않았다.

 

따라서 Si와 Ti값을 갱신해준다.

 

	Si	Ti	Ri	Qi
i = 0	1	0	26
i = 1	0	1	8	3
i = 2	1 (1 - 0*3)	-3 (0 - 1*3)	2

 

 

이제 다음 과정을 다시 갱신해준다.

 

 

	Si	Ti	Ri	Qi
i = 0	1	0	26
i = 1	0	1	8	3
i = 2	1	-3	2	4
i = 3			0

 

 

이때 Ri가 0이 되었으니 우리는 여기서 결과값을 파악 할 수 있게 된다. 

 

즉, 26s + 8t = 2는 26*1 + 8*(-3) = 2임을 알 수 있게 된다.

 

 

 

 

 

3. 확장 유클리드 알고리즘 소스 코드

 

위의 내용을 이용하면 충분히 코드를 구현 할 수 있으므로 구현 방법은 생략합니다.

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct INFO {
    int gcd;
    int s;
    int t;
};
vector<int> s, t, r, q;
INFO xGCD(int a, int b) {
    s = { 1,0 };
    t = { 0,1 };
    r = { a,b };
 
    while (1)
    {
        int r2 = r[r.size() - 2];
        int r1 = r[r.size() - 1];
        q.push_back(r2 / r1);
        r.push_back(r2 % r1);
        
        if (r[r.size() - 1] == 0)
            break;
 
        int s2 = s[s.size() - 2];
        int s1 = s[s.size() - 1];
 
        int t2 = t[t.size() - 2];
        int t1 = t[t.size() - 1];
        
        int q1 = q[q.size() - 1];
        s.push_back(s2 - s1 * q1);
        t.push_back(t2 - t1 * q1);
    }
 
    // return gcd, s, t
    INFO ret = { r[r.size() - 2], s[s.size() - 1], t[t.size() - 1] };
 
    s.clear(), t.clear(), r.clear(), q.clear();
 
    return ret;
}
int main()
{
 
    int a, b;
    scanf("%d %d", &a, &b);
    if (b > a)
        swap(a, b);
    INFO ret = xGCD(a, b);
 
    printf("gcd :: %d s :: %d t :: %d", ret.gcd, ret.s, ret.t);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

 

 

 

 

 

 

4. 나머지 연산 곱셈 역수(역원) 구하기

 

확장 유클리드 알고리즘을 이용하면 곱셈의 역원도 구할 수 있게 된다.

 

우선 역원을 구하기 전에 알아야 할 사항은

 

곱셈의 역원이 존재한다는 것은 두 수가 서로소라는 건데, a⋅s≡1 (mod p) 를 만족시키는 s를 찾을 수 있다는 의미이다.

 

 

예를들어보자.

 

(13 / 14) mod 11은 뭘까?

 

이를 우선 (13 * 14^-1) mod 11로 나타내보자.

 

그리고 모듈러 곱셈의 원리에 의해 (2 * 3^-1) mod 11로 나타내보자.

 

이제 3^-1 mod 11이 무엇인지 알아내야 한다.

 

우리는 a*s + b*t = gcd(a,b)를 알고있다.

 

따라서 11과 3을 각각 넣어 t의 값을 관찰해내면 우리는 역원값을 구할 수 있게 된다.

 

즉, 11*s + 3*t = gcd(11,3) = 1

 

이때 mod 11을 하면 11*s mod 11 = 0이 되니 결국 3*t = 1이 된다.

 

이를 알기위해 확장 유클리드 알고리즘을 이용하여 t를 구하면 우리가 원하는 곱셈의 역원을 알 수 있게 된다.

 

이때 t값이 음수가 나오면 + mod값을 해주어 양수로 변환시키자.

 

 

결국 위의 코드에 11 3을 입력하면

gcd :: 1 s :: -1 t :: 4가 나타난다.

 

즉 t값인 4가 역원이 된다는 것이다.