×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 1,680,603명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
728x90
반응형

 

 


목차

 

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

 

i = 1

⌊ 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. 확장 유클리드 알고리즘 소스 코드

 

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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,};
    t = { 0,};
    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 >>
Crocus

 

 

 

 

 

 

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가 역원이 된다는 것이다.
 
 
 

 

 

 

반응형
  1. ㅁㅁ 2020.02.21 17:08

    잘보고갑니다! 중간에 주소에 삭제조취->삭제조치 오타있어용!