Python 중국인의 나머지 정리

@medium, Mr. Viraj Shelar

Chinese Remainder Theorem

(중국인의 나머지 정리, 이하 CRT)

 

소개

CRT는 손자산경에, (손자병법 손자 아님),

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고,7로 나누었을 때 2가 남는 수는 무엇인가?

간단해보이지만, 일반 방정식으로 해결하려해보면 꽤나 복잡하다.

필요한 사전 지식은, 연합 합동식을 알아야한다.

이 글에선, 식의 증명보다는 실제 몇 예제를 통해 문제를 푸는 법과, 파이썬 코드로 작성만 해볼 것이다.

(증명은 맨 아래 참고 사이트를 이용)

---

합동식이란?

합동식만 먼저 설명하자면,

$m~|~(a - b)$ 일 때 (m이 a-b로 나누어 떨어질 때),

a는 법(modular) m에 대하여 b와 합동이다.

기호는 $a ≡ b~(mod~m)$

ex) $15 ≡ 1~(mod~2)$ (15를 2로 나눈 나머지는 1)

---

문제 풀이 예제

모든 m은 서로 서로소 관계일 때 적용된다.

서로소가 아니면 서로소 상태로 만들어야한다.

$N$ 은 모든 m의 곱

$n_i$ 는 mod m을 의미

$a_i$ 는 나머지를 의미

$\bar{n_i}$ 는 모든 m을 곱한 후 $n_i$로 나눈 몫

$u_i$ 는 ($\bar{n_i} * u_i ≡ 1$) 에서 구한 $u_i$

결과식 = $\sum_{i=1}^N$ ($a_i$ * $\bar{n_i}$ * $u_i$)

 

1. 손자산경

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고,7로 나누었을 때 2가 남는 수는 무엇인가?

= 식으로 표현하면 아래와 같다.

$x ≡ 2~(mod~3)$

$x ≡ 3~(mod~5)$

$x ≡ 2~(mod~7)$

 

$ N = 3 * 5 * 7 = 105$

$n_i$	$a_i$	$\bar{n_i}$	$u_i$
3	2	N / 3 = 35	$35*u_1 ≡ 1~(mod~3)$  $\therefore{u_1 = 2}$
5	3	N / 5 = 21	$21*u_2 ≡ 1~(mod~5)$  $\therefore{u_2 = 1}$
7	2	N / 7 = 15	$15*u_3 ≡ 1~(mod~7)$  $\therefore{u_3 = 1}$

(※ 왜 35 * u1 ≡ 1에서 u1이 2가 나오냐면, 그냥 아무 수나 골라서 넣어 해답을 찾음)

(35 * 2 % 3 = 1)

 

즉, 답은

x =

$a_1 * \bar{n_1} * u_1 + ... + a_3 * \bar{n_3} * u_3$

≡ $2 * 35 * 2 + 3 * 21 * 1 + 2 * 15 * 1$

≡ $233~(mod~105)$ 

≡ $233~\%~105~(mod~105)$

≡ $23~(mod~105)$

$\therefore{x = 23}$

 

2. 서로소가 아닌 상태

문제

$x ≡ 1~(mod~2)$

$x ≡ 1~(mod~3)$

$x ≡ 1~(mod~4)$

$x ≡ 1~(mod~5)$

$x ≡ 1~(mod~6)$

 

1. 우선 m들이 모두 서로소 관계를 가져야 함.

2. 겹치는 수 아무거나 골라서 분해, (mod 6) 식을 골라서 분해해보면

mod 2와 mod 3로 나눌 수 있다.

$x ≡ 1~(mod~6) \begin{cases} x ≡ 1~(mod~2) \\ x ≡1~(mod~3)\end{cases}$

 

3. $(mod~4)$는 $(mod~2)$를 포함하고, $(mod~3)$는 중복이므로

문제는 아래와 같이 바뀐다.

$x ≡ 1~(mod~3)$

$x ≡ 1~(mod~4)$

$x ≡ 1~(mod~5)$

 

$ N = 3 * 4 * 5 = 60$

$n_i$	$a_i$	$\bar{n_i}$	$u_i$
3	1	N / 3 = 20	$20*u_1 ≡ 1 (mod 3)$  $\therefore{u_1 = 2}$
4	1	N / 4 = 15	$15*u_2 ≡ 1 (mod 4)$  $\therefore{u_2 = 3}$
5	1	N / 5 = 12	$12*u_3 ≡ 1 (mod 5)$  $\therefore{u_3 = 3}$

 

즉, 답은

x =

$a_1 * \bar{n_1} * u_1 + ... + a_3 * \bar{n_3} * u_3$

≡ $1 * 20 * 2 * + 1 * 15 * 3 + 1 * 12 * 3$

≡ $121~(mod~60)$ 

≡ $121~\%~60~(mod~60)$

≡ $1~(mod~60)$

$\therefore{x = 1, 61 ...}$

파이썬

# Python 3.6
from functools import reduce


def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a * b, n)  # n 값 모두 곱하기
    for n_i, a_i in zip(n, a):
        p = prod // n_i  # bar n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod


def mul_inv(a, b):  # Modular inverse
    b0 = b
    x0, x1 = 0, 1
    if b == 1:
        return 1
    while a > 1:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += b0
    return x1


if __name__ == "__main__":
    n = [3, 5, 7]
    a = [2, 3, 2]
    print(chinese_remainder(n, a))  # 23

    n = [3, 4, 5]
    a = [1, 1, 1]
    print(chinese_remainder(n, a))  # 1

 

참고

나무위키 - 중국인의 나머지 정리

DirectKnowledge - Chinese Remainder Theorem

MathStackExchange - CRT for non-prime / non-coprime moduli