주어진 합성수 n=pq (여기서 p와 는 소수)의 법 아래에서 임의의 정수 가 2차 잉여류인지 여부를 결정하는 문제는, 의 소인수 p와 가 알려져 있지 않을 경우 매우 어려운 문제로 알려져 있습니다.
가 법 에 대한 이차 잉여류라는 것은 w2 ≡ u mod n을 만족하는 w가 존재함을 의미합니다.
| 정의.1 |
| 법 n = p*q에 대한 2차 잉여류 u가 존재할때, a mod p와 a mod q는 각각 법 p,q에 대한 2차 잉여류이다. 만약 up= u mod p, uq = u mod q라 하면, u가 법 n에 대한 2차 잉여류이면 w2 ≡ u (mod n)을 만족하는 제곱근 w가 존재하고 w2 ≡ u (mod p) 또는 w2 ≡ u (mod q)가 성립한다. 따라서, w2 ≡ up (mod p) 그리고 w2 ≡ uq (mod q)이기 때문에 up = u mod p와 uq = u mod q는 각각 법 p와 q에 대한 2차 잉여류가 된다. 법 p에 대한 up의 제곱근{x1,y1}, 법 q에 대한 uq의 제곱근{x2,y2}이라하자. 중국인의 나머지 정리에 의해 각각의 쌍을 만족하는 4쌍의 w가 존재한다. w ≡ x1 (mod p), w ≡ x2 (mod q) w ≡ x1 (mod p), w ≡ y2 (mod q) w ≡ y1 (mod p), w ≡ x2 (mod q) w ≡ y1 (mod p), w ≡ y2 (mod q) |
예제 1. 두 소수 p = 17, q = 13 일 때, 법 n = p*q = 221에 대한 이차 잉여류는 법 p와 q에 대해서 각각의 제곱근을 가진다.
법 p = 17에 대한 제곱근 쌍 = { x1 = 2, y1 =15 } -> up = 4일때, w2 ≡ 4 (mod 17)
법 q = 13에 대한 제곱근 쌍 = { x2 = 2, y2 =11 } -> uq = 4일때, w2 ≡ 4 (mod 13)
▷ 각각의 쌍을 만족하는 4쌍의 w가 존재한다.
w ≡ 2 (mod 17), w ≡ 2 (mod 13)
w ≡ 2 (mod 17), w ≡ 11 (mod 13)
w ≡ 15 (mod 17), w ≡ 2 (mod 13)
w ≡ 15 (mod 17), w ≡ 11 (mod 13)
▷중국인의 나머지 정리로 계산하여 네 개의 제곱근 값을 찾을 수 있다.
1) w = (n/p)·Q1·x1 + (n/q)·Q2·x2 mod n = (13)(4)(2) + (17)(10)(2) mod 221 = 2
2) w = (n/p)·Q1·x1 + (n/q)·Q2·y2 mod n = (13)(4)(2) + (17)(10)(11) mod 221 = 206
3) w = (n/p)·Q1·y1 + (n/q)·Q2·x2 mod n = (13)(4)(15) + (17)(10)(2) mod 221 = 15
4) w = (n/p)·Q1·y1 + (n/q)·Q2·y2 mod n = (13)(4)(15) + (17)(10)(11) mod 221 = 219
▷ 계산확인
1) 22 mod 221 = 4
2) 2062 mod 221 = 4
3) 152 mod 221 = 4
4) 2192 mod 221 = 4
각 조합으로 중국인의 나머지 정리를 적용하면 총 4개의 서로 다른 w값을 얻게 된다. 이 값들은 모두 법 n = 221에서 u의 제곱급이 된다.