-
Python 중국인의 나머지 정리컴퓨터/파이썬 2020. 9. 25. 15:38728x90반응형
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
참고
728x90'컴퓨터 > 파이썬' 카테고리의 다른 글
Python Fast inverse square root (23) 2020.09.28 Python Karatsuba(카라추바) 곱셈 알고리즘 (8) 2020.09.24 파이썬 Jest pytest 이용하기 (0) 2020.09.22