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

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

 

 


목차

 

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

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