중국인의 나머지 정리 구현해보기

#blog#ruby#math

중국인의 나머지 정리

생각보다 자주 나온다

정수론 문제를 풀다 보면 심심찮게 중국인의 나머지 정리(Chinese Remainer Theorem) 로 풀리는 문제들을 만나볼 수 있습니다.

매번 기본 원리랑 구현을 까먹는 것도 그러니 한 번 정리해 보고자 합니다.

기본 개념

$1$보다 큰 정수 $n_1, ... , n_k$가 있고, 각각의 $n_i$보다 작고 $0$보다 크거나 같은 정수 $a_1, ..., a_k$가 있다고 합시다.

이 때, 각각의 $n_i$들의 순서쌍이 모두 서로소라면, 모든 $n_i$들의 곱을 $N$이라고 했을 때,
각각의 방정식 $x \equiv a_i\ (\mathrm{mod}\ n_i)$ 들에 대해 $0 \leq x < N$인 유일한 정수해 $x$가 존재한다는 것이 바로 중국인의 나머지 정리입니다.

즉,
$$\begin{align*} x &\equiv a_1\ (\mathrm{mod}\ n_1) \\ x &\equiv a_2\ (\mathrm{mod}\ n_2) \\ &\vdots \\ x &\equiv a_k\ (\mathrm{mod}\ n_k) \end{align*}$$
에 대해 $0 \leq x < N$인 유일한 정수해 $x$가 존재한다는 뜻입니다.

그리고 이 식들이 복수의 해를 가진다면, 그 해들은 모두 $\mathrm{mod}\ N$에 대해 동치입니다.

구현

중국인의 나머지 정리를 구현하기 위해서는 다음과 같은 단계가 필요합니다.

  1. 각 $n_i$에 대한 $N_i = \frac{N}{n_i}$를 계산합니다.
  2. 각 $N_i$에 대한 $M_i$를 계산합니다. 여기서 $M_i$는 $N_i$의 모듈러 역수입니다.
  3. 최종 해는 $x = \sum_{i=1}^{k} a_i \cdot N_i \cdot M_i \ (\mathrm{mod}\ N)$로 계산됩니다.

여기서 모듈로 역수를 계산하기 휘해 확장 유클리드 알고리즘을 사용할 수 있습니다.
$n_i$가 소수인 경우에는 페르마의 소정리를 이용할 수도 있습니다.

Ruby를 이용한 구현 예시는 다음과 같습니다.

def mul_inv(a, b)
  # Extended Euclidean Algorithm to find the modular inverse of a mod b
  b0 = b
  x0, x1 = 0, 1
  return 1 if b == 1
  while a > 1
    q = a / b
    a, b = b, a % b
    x0, x1 = x1 - q * x0, x0
  end
  x1 += b0 if x1 < 0
  x1
end
 
def crt(congruences)
  # Chinese Remainder Theorem implementation
  prod = congruences.reduce(1) { |acc, (_, mod)| acc * mod }
  sum = congruences.reduce(0) { |acc, (rem, mod)| acc + rem * (prod / mod) * mul_inv(prod / mod, mod) }
  sum % prod
end

물론, 이 구현은 각 $n_i$가 서로소라는 가정 하에 작동합니다.

확장

지금까지는 $n_i$가 서로소라는 가정 하에 생각했지만, 좀 더 일반적인 경우도 생각해 볼 수 있습니다.

모듈로 합동식의 $x$의 계수가 $1$이 아닌 경우, 그리고 $n_i$가 서로소가 아닌 경우에도 중국인의 나머지 정리를 적용할 수 있습니다.
이 경우, 각 식을 $x \equiv a_i \ (\mathrm{mod}\ n_i)$ 꼴로 바꾸고, $n_i$가 서로소가 아닌 경우에는 두 합동식을 하나로 합치는 작업을 거쳐 일반화할 수 있습니다.

계수를 $1$로 만드는 과정은 모듈로 역수를 이용하면 되고, 두 모듈로 합동식은 최대공약수와 최소공배수를 이용해 다음과 같이 합칠 수 있습니다.
($p, q$는 확장 유클리드 알고리즘을 통해 찾아낸 $n_1, n_2$의 계수, 자세한 증명은 참고 문헌의 링크에)

$$ \begin{align*} x &\equiv a_1\ (\mathrm{mod}\ n_1) \\ x &\equiv a_2\ (\mathrm{mod}\ n_2) \end{align*} \rightarrow x \equiv a_1\frac{n_2}{g}p + a_2\frac{n_1}{g}q\ (\mathrm{mod}\ LCM(n_1, n_2)) $$

$n$개의 합동식이 있을 때, 이를 반복적으로 합쳐 나가면 최종적으로 하나의 합동식으로 만들 수 있고, 이것이 우리가 구하고자 하는 해가 됩니다.
만약, 이 과정에서 모순이 발생한다면 해가 존재하지 않습니다.

이 과정을 코드로 구현하면 다음과 같습니다.

def extended_gcd(a, b)
  # Extended Euclidean Algorithm (non-recursive)
  # Returns [gcd, x, y] where gcd = a*x + b*y
  
  old_r, r = a, b
  old_s, s = 1, 0
  old_t, t = 0, 1
  
  while r != 0
    quotient = old_r / r
    old_r, r = r, old_r - quotient * r
    old_s, s = s, old_s - quotient * s
    old_t, t = t, old_t - quotient * t
  end
  
  [old_r, old_s, old_t]
end
 
def crt_general(congruences)
  # General Chinese Remainder Theorem implementation
  # Returns [x, m] where x is the solution and m is the modulus
 
  a0 = congruences[0][0]; m0 = congruences[0][1]
  congruences[1..].each do |(a1, m1)|
    g = m0.gcd(m1)
    return [-1, -1] if (a0 - a1) % g != 0 # No solution
    gg, pp, qq = extended_gcd(m0 / g, m1 / g)
    mod = m0.lcm(m1)
    x = (a0 * (m1 / g) * qq + a1 * (m0 / g) * pp) % mod
    x += mod if x < 0
    a0, m0 = x, mod
  end
  [a0 % m0, m0]
end

용도

문제들을 잘 분석해 봤을때 위에서 설명한 대로 나머지의 조건들이 주어지고, 그 해를 구하는 문제들이 종종 있습니다.
이런 경우 중국인의 나머지 정리를 이용하면 쉽게 해를 구할 수 있습니다.

참고 문헌

https://en.wikipedia.org/wiki/Chinese_remainder_theorem
https://rosettacode.org/wiki/Chinese_remainder_theorem
https://forthright48.com/chinese-remainder-theorem-part-2-non-coprime-moduli