알고리즘: 확장 유클리드 호제법

우선 유클리드 호제법을 먼저 공부하고 보자!!

https://qktjwl123.tistory.com/97

알고리즘: 유클리드 호제법(최대공약수, gcd)

---

모듈러 역수란?

확장 유클리드 알고리즘은 모듈러 역수를 구하는 알고리즘이다.

모듈러 역수란 A*B (mod C) = 1이 되게하는 B를 뜻한다. (A와 C는 주어지고 B를 구해야한다.)

*모듈러 역수는 A와 C가 서로소일 경우에만 존재한다.

*GCD(A, C) = 1인 경우

 

A (mod C)의 모듈러 역수를 구하는 단순한 방법은 다음과 같다.

for (int i=1; i<c; i++) {
    if ((a*b) % c == 1) {
        x = i;
        break;
    }
}

1. 0에서 C-1까지 B에 다 넣어보며 A * B mod C 를 계산한다. (부르트포스)
2. A mod C의 모듈러 역수는 A * B mod C = 1을 만족하는 B값이다.

---

확장 유클리드 호제법:

이는 느리기 때문에 확장 유클리드 호제법으로 시간을 단축할 수 있다.

유클리드 호제법은 다음과 같은 성질을 이용한다.

• GCD(A,0) = A
• GCD(0,C) = C
• A = C⋅Q + R이고 C≠0이면 GCD(A,C) = GCD(C,R) 이때 Q는 정수, R은 0에서 B-1의 정수

이때 A, B가 서로소인 경우 GCD(A, B)는 1을 반환한다. (최대공약수가 1이니)

이를 역으로 계산해보면 모듈러 역수를 구할 수 있고 과정은 다음과 같다.

GCD(4, 7)

1. GCD(4, 7) - 4과 7의 최대공약수 찾기
   • A=4, B=7
   • A ≠ 0
   • B ≠ 0
   7 = 4 * 1 +3
2. GCD(4,7)=GCD(4,3) - 이기 때문에 4와 3의 최대공약수 찾기
   • A=4, B=3
   • A ≠0
   • B ≠0
   4 = 3 * 1 + 1
3. GCD(4,3)=GCD(3,1) - 이기 때문에 3과 1의 최대공약수 찾기
   • A=3, B=1
   • A ≠0
   • B ≠0
   3 = 1 * 3 + 0
4. GCD(4,7) = GCD(4,3) = GCD(3,1) = GCD(1,0) = 1

GCD(4, 7)은 위와 같은 식으로 4*s+7*t=1로 표현된다.

 

c언어로 작성한 코드:

int xGCD(int a, int c, int &x, int &y)
{
  if (c == 0)
  { 
    x = 1; y = 0; return a;
  }
  int x1, y1, gcd = xGCD(c, a%c, x1, y1);
  x = y1;
  y = x1 - (a/c) * y1;
  return gcd;
}

https://www.acmicpc.net/problem/14565