[수학] 조합을 구하는 다양한 방법들 - (2)

이번 시간에는...

---

이번 시간에는 시도해 볼 수 있는 방법중 하나로 확장 유클리드 호제법을 사용해보자. 사실 조합을 구할 때 확장 유클리드 호제법이 쓰이는 일은 잘 없다(대부분 모듈러 연산을 위해 소수를 제시하고, 페르마 소정리를 이용해 풀 수 있기 때문이다). 하지만 확장 유클리드 호제법 역시 다양한 상황에서 사용될 수 있고, 특히 CS에서는 현대 암호학의 근간인 RSA 알고리즘에도 사용되므로 깊게 이해하고 넘어가보자.

 

 

확장 유클리드 호제법

---

 

이 포스팅에서도 정리된 바 있지만..

 

2023.12.05 - [알고리즘 문제/백준] - [백준/3955] 캔디 분배 (Python)

[백준/3955] 캔디 분배 (Python)

 

확장 유클리드호제법을 다시금 정리해 보고자 한다. 위 포스팅에서는 귀납적 정의가 제대로 되지 않았던 점도 있어서...

 

 

유클리드 호제법을 통하여 우리는 a, b에 대해서 a = r0, b = r1라고 둔다면,

 

꼴로 재귀적으로 나타낼 수 있다. 이 때 gcd(a, b) = gcd(b, r2) = .... gcd(rn, 0) = rn임이 유클리드 호제법을 통해 증명되며, 이를 통하여 두 수의 최대공약수를 구하는 데 이용할 수 있는 방식이다.

여기서 더 나아가, 각 a, b에 대하여 ax + by = gcd(a, b)를 만족하는 최적의 x, y를 구하고자 한다. x, y에 대해 다음과 같이 정의하자.

 

라고 둔다면, 초항은

 

로 나타난다. 일반항을 다음과 같이 나타내자.

그렇다면,

가 되므로, 귀납적으로 위 일반항이 옳음이 증명된다.

즉 앞서 rn = gcd(a, b)인 상황에서 xn, yn의 값을 구할 수 있으며, 이는 배주 항등식을 만족하는 정수쌍이다. 또한, 배주 항등식에 따라 이를 만족하는 (xn, yn) 정수쌍이 반드시 존재함이 보장된다. 이러한 유클리드 호제법을 이용한 정수쌍 (xn, yn)을 구하는 방식을 확장된 유클리드 호제법이라고 볼 수 있겠다.

 

 

 

확장 유클리드 호제법의 적용 - 조합의 경우

---

확장 유클리드 호제법은 다음과 같은 알고리즘에서 쓰일 수 있다.

 

• 모듈러 역원 구하기
• RSA 알고리즘

 

그리고 오늘, 모듈러 역원을 구할 수 있다는 장점을 가지고 조합 문제에 도전해 보도록 하자.

 

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

16134번: 조합 (Combination)

 

이 문제는 N, R의 값이 매우 크며, 모듈러 연산을 위한 식 P가 소수로 주어져 있다. 앞선 포스팅에 따라, 페르마의 소정리를 이용하는 방법을 먼저 생각해보자. 

 

• C(n, r) = n! / ( r! * (n - r)! ) 로 정의되고, 여기서 분모에 위치하는 r! * (n - r)! 의 모듈러 연산 역원을 구하면 된다.
• P가 소수이니, 이 r! * (n - r)! 에 대한 모듈러 역원은  (r! * (n - r)!)^(p-2)가 된다.
• 즉 n!까지의 값을 먼저 구한 다음, 각 값을 대입하고 모듈러 역원을 구하면 끝난다. 제곱 연산은 분할 정복으로 빠르게 구할  수 있다.

 

...이 문제는 확장 유클리드 호제법을 통해서도 해결할 수 있다. 페르마의 소정리를 이용한 풀이는 다음 코드와 같이 나타난다.

 

MOD = 1000000007
N, R = map(int, input().split())
num = 1
a, b = 1, 1
for i in range(1, N+1) :
  num = (num * i) % MOD
  if i == N :
    a = (a * num) % MOD
  if i == R :
    b = (b * num) % MOD
  if i == N-R :
    b = (b * num) % MOD
    
def pow(n, p) :
  if p == 1 :
    return n

  pval = pow(n, p // 2) % MOD
  pval = pval * pval % MOD
  if p % 2 :
    return pval * n % MOD
  return pval
  
print(a * pow(b, MOD-2) % MOD)

 

 

 

우선, a에 대한 모듈러 연산의 역원이 x라고 할 때, 

이 만족된다. 즉

 

 

이라는 식으로 변형해 볼 수 있다. (y는 정수) 또한, P는 소수이므로 a != 1이라면 gcd(a, P) = 1이다. 따라서

 

가 된다. 즉 확장 유클리드 호제법으로 정수쌍 (x, y)를 구할 수 있으며, 이 때 x 는 a 에 대한 모듈러 역원임이 자명하다.

 

def extend_euclidean(n, P) :
  a, b = n, P
  x0, x1 = 1, 0
  y0, y1 = 0, 1

  while b :
    q = a // b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
    a, b = b, a % b
  if x0 < 0 :
    x0 += P
    
  return x0

 

다음과 같이 모듈러 역원을 구하고...

 

print(a * extend_euclidean(b, MOD) % MOD)

 

이를 출력하면 끝난다. 전체 코드는 다음과 같다 :

 

MOD = 1000000007
N, R = map(int, input().split())
num = 1
a, b = 1, 1
for i in range(1, N+1) :
  num = (num * i) % MOD
  if i == N :
    a = (a * num) % MOD
  if i == R :
    b = (b * num) % MOD
  if i == N-R :
    b = (b * num) % MOD
    
def extend_euclidean(n, P) :
  a, b = n, P
  x0, x1 = 1, 0
  y0, y1 = 0, 1

  while b :
    q = a // b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
    a, b = b, a % b
  if x0 < 0 :
    x0 += P
    
  return x0

print(a * extend_euclidean(b, MOD) % MOD)

 

 

위가 페르마의 소정리 + 제곱 분할정복을 이용한 풀이, 아래가 확장 유클리드 호제법을 이용한 풀이이다. 거의 시간차가 나지 않음을 알 수 있다.

 

페르마의 소정리는 P가 소수이거나 유사 소수(카마이클 수, 소수가 아님에도 페르마의 소정리를 만족하는 P값들)일 때 유용하게 사용할 수 있겠다. 확장 유클리드 알고리즘은 이러한 적용 시 a, P가 서로소이기만 하면 gcd(a, P) = 1이므로 적용 가능하다.

 

베주 항등식에 대해서는 정리나 증명에 대해 넘어가지 않은 점이 아쉬우나, 거기까지 파고 들어가면 포스팅의 목적을 많이 벗어나는 것 같아 제외했다. 또한, 확장 유클리드 호제법, 페르마 소정리의 일반화 버전인 오일러 정리, 그리고 분할 정복 제곱 등이 종합적으로 쓰이는 RSA에 대해서도 다음에 한 번 다루어보면 좋을 것 같다.

 

..포스팅이 더 길어진다... 다음에는 뤼카의 정리를 한 번 다루어보자.