[CryptoHack] Chinese Remainder Theorem

 

개념 설명

---

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

 

중국인의 나머지 정리는 모듈리(mod p에서 p)가 서로소(coprime)일 경우 선형 합동 집합에 대한 특수한 해를 제공한다.

즉, 임의의 정수 집합 $a_i$와 pairwise(쌍) 서로소(paiwise coprime integers) $n_i$가 주어졌을 때 다음과 같은 선형 합동식이 성립한다.

 

! 참고로, "pairwise coprime integers"는 우리가 정수 집합 ${n_1, n_2, ..., n_i}$를 가지고 있을 때, 집합에서 선택된 모든 정수 쌍은: $\gcd(n_i, n_j) = 1$임을 의미한다.

 

$ x \equiv a_1 \mod n_1$

$ x \equiv a_2 \mod n_2$

. . .

$x \equiv a_n \mod n_n$

 

$N = n_1 * n_2 * ... * n_n$에서(n 집합에서 아무거나 뽑아도 서로소라는 뜻) $x \equiv a \mod N$인 특수한 해가 있다.

암호학에서, 우리는 일반적으로 매우 큰 정수의 문제를 몇 가지 더 쉬운 문제의 집합으로 줄이기 위해서 중국인의 나머지 정리를 사용한다.

다음과 같은 선형 합동 집합이 주어졌을 때

 

$x \equiv 2 \mod 5$

$x \equiv 3 \mod 11$

$x \equiv 5 \mod 17$

 

$x \equiv a \mod 935$인 정수 a를 찾아라.

 

! 가장 큰 모듈러 합동식으로 시작하여, $x \equiv a \mod p$를 위해 우리는 임의의 정수 k에 대해 $x = a + k*p$를 적을 수 있다.

 

풀이

---

x = 5
while True :
	if x % 11 == 3 :
		if x % 5 == 2 :
			print(x)
			break
		else :
			x += 17 * 11
	x += 17

 

연립 합동식인듯?

중국인의 나머지 정리를 검색해보니 연립 합동식을 푸는.. 

선형 합동 집합이 선형 연립 합동식이구나.

 

모듈러를 처음에는 17에 만족하도록 증가하면서

하나 걸리면 그것까지 동시에 증가시키고.. 이제 모든 모듈러를 만족시키는 첫 숫자를 출력한다.