Chinese Remainder Theorem 중국인 나머지 정리

오늘의 마지막 포스팅은 '중국인의 나머지 정리' 입니다. RSA 에 중요한 정리임으로 꼭 알아두셔야합니다!

 

중국인의 나머지 정리란?

-> 어떤 정수 값은 서로소 관계에 있는 moduler의 나머지 값으로 표현될 수 있다.

 

예를 들어 Z10 공간엔 10개의 정수 0~9가 존재합니다. 그럼 이 수 들은 modulo 2 와 5로 표현이 가능 합니다. 

r2 = 0 고 r5 = 3 이면 8입니다. (2와 5는 서로소 관계입니다.)

 

이렇게 2와 5처럼 modulo 연산을 시행하는 수를 mi 라고 표현합니다. 그리고 mod M = m1m2m3 ...mk로 구성이 됩니다. 중국인의 나머지 정리(CRT)의 핵심은 큰 연산을 작은 연산으로 쪼개줌에 있습니다.

 

 

CRT

m1,m2,m3,m4..mn 은 pairwise relatively prime 이면 어떤 수 x 를 표현하기 위해 연립 1차 합동식을 만들 수 있습니다. 

 

x ≡ b1(mod m1)

x ≡ b2(mod m2) 

x ≡ b3(mod m3) 

.

.

.

x ≡ bn(mod mn)

 

 

큰 공간 m에 존재하는 x는 작은 공간(mi)에서 표현됩니다. 즉 x 는 복원이 가능함을 의미합니다. 

m = m1m2m3...mn 에 대하여 단 하나의 해를 가집니다. 

 

이 연립 1차 합동식을 구하기 위해서는 Mi = m/mi로 놓아서 

m = Mimi, gcd(mi,Mi) = 1 이므로

MiNi  ≡ 1 mod mi 을 성립하는 역원 Ni가 존재합니다. 

 

x ≡ ∑biMiNi(mod m)

  ≡ b1M1N1 + b2M2N2 + b3M3N3(mod m)

 

 

CRT 의 원리

m1,m2,m3 가 서로소이고 m = m1m2m3 이므로 

x ≡ b1M1N1 + b2M2N2 + b3M3N3 (mod m) 이라 두면  

x ≡ b1(mod m1) 

x ≡ b2(mod m2) 

x ≡ b3(mod m3) 

 

x ≡ b1M1N1 + b2M2N2 + b3M3N3 (mod m1)

  ≡ b1M1N1(mod m1) [ M2≡0,M3≡0(mod m1)]

  ≡ b1(mod m1)( M1N1  ≡1(mod m1))

 

 

CRT 는 큰 공간에서 작은 수로 쪼개서 계산을 할 수 있습니다.

 

(A + B)mod M <->((a1 + b1)mod m1, ... (ak + bk) mod mk)

(A - B)mod M <->((a1 - b1)mod m1, ... (ak - bk) mod mk)

(A x B)mod M <->((a1 x b1)mod m1, ... (ak x bk) mod mk)

 

 

보안에 활용되는 매우 큰 수인 M을 작은 수 mi 들로 계산할 수 있어 연산의 가속화를 가능케 합니다.

 

오늘은 CRT 에 대해 알아봤습니다. 수고 많으셨습니다.