중국인의 나머지 정리(CRT)
| 정리.1 |
| r개의 정수 p1, p2, ..., pr 이 주어졌을 때, 임의의 두 정수에 대해서 서로 소의 관계에 있다면, i ≠ j 에 대해서 gcd( pi , pj ) = 1 이면, 연립 합동식 x ≡ xi (mod pi) i = 1, 2, ..., r에는 법 n = p1·p2· ... ·pr에 유일한 해가 존재한다. x = [ ∑ (n/pi)·qi·xi ] mod n (범위: i = 1부터 r 까지) 이때 qi는 법 pi에 대한 (n/pi)의 곱셈상의 역원이 된다. |
예제 1. x ≡ 3 (mod 11), x ≡ 7 (mod 17)의 연립합동식?
→ p1 = 11, p2 = 17, 서로소의 관계 법 n = p1*p2 = 11*17 = 187
→ 곱셈상의 역원을 각각 구한다.
식① (n/p1)·q1 mod p1 = 1
(187/11)·q1 mod 11 = 1,
17·q1 ≡ 1 (mod 11), 곱셈상 역원 q1 = 2.
식② (n/p2)·q2 mod p2 = 1,
(187/17)·q2 mod 17 =1,
11·q2 ≡ 1 (mod 17), 곱셈상 역원 q2 = 14.
∴ X = (n/p1)∙q1∙x1 + (n/p2)∙q2∙x2 = 17*2*3 +11*14*7 mod 187 = 58.
1) x ≡ 3 (mod 11)에 대한 계산검증: 58 mod 11 = 3
2) x ≡ 7 (mod 17)에 대한 계산검증: 58 mod 17 = 7
예제 2. x ≡ 3 (mod 11), x ≡ 7 (mod 17), x ≡ 18 (mod 23)의 연립합동식?
→ p1 = 11, p2 = 17, p3 = 23 서로소의 관계 법 n = p1*p2*p3 = 11*17*23 = 4301
→ 곱셈상의 역원을 각각 구한다.
식① (n/p1)·q1 mod p1 = 1
(4301/11)·q1 mod 11 = 1,
391·q1 ≡ 1 (mod 11), 곱셈상 역원 q1 = 2.
식② (n/p2)·q2 mod p2 = 1,
(4301/17)·q2 mod 17 =1,
253·q2 ≡ 1 (mod 17), 곱셈상 역원 q2 = 8.
식③ (n/p3)·q3 mod p3 = 1,
(4301/23)·q3 mod 23 =1,
187·q3 ≡ 1 (mod 23), 곱셈상 역원 q3 = 8.
∴ X = (n/p1)∙q1∙x1 + (n/p2)∙q2∙x2 + (n/p3)∙q3∙x3 = 391*2*3 + 253*8*7 + 187*8*18 mod 4301 = 432.
1) x ≡ 3 (mod 11)에 대한 계산검증: 432 mod 11 = 3
2) x ≡ 7 (mod 17)에 대한 계산검증: 432 mod 17 = 7
3) x ≡ 18 (mod 23)에 대한 계산검증: 432 mod 23 = 18
| ※ 곱셈상의 역원 |
| /* 곱셈상이 역원은 주어진 수와 곱했을 때 곱의 결과가 1이 되는 수. 정수 a가 법 m에 대해 역원을 갖는 식 a* (1/a) ≡ 1 (mod m) - a와 m이 서로소가 아니면, 역원은 존재하지 않는다. - a와 m가 서로소 gcd (a, m) =1이면, 유클리드 확장알고리즘으로 역원을 구할 수 있다. Parameter: a, m return: 역원 */ function modInverse (a, m) { var ext = extend_Euclid(a, m); // 유클리드 확장 알고리즘 참고 if (ext.gcd != 1) { return -1; } return (ext.x % m + m) % m; // x값이 음의 수이면, 양의 수로 변환 } |
.