홀수의 소수 p에 대해, 이차 합동 관계 a·x2 + b·x + c ≡ 0 (mod p), (a ≠ 0)가 주어졌을 때, 이를 단순히 나타내기 위해 x → (x - b)/2a로 치환하고 특정형태로 변형할 수 있다. 그 결과는 다음과 같은 합동식으로 나타낼 수 있다.
x2 ≡ k (mod p)
| 정의.1 |
| 홀수 소수를 p라 두고, p로 나누어지지 않는 정수를 k라하자. 합동식 x2 ≡ k (mod p)을 만족하는 어떤 x가 존재하면 k를 "이차 잉여(Quadratic Residue, QR)"라고 부른다. 만약 그러한 x가 존재하지 않으면, k를 "이차 비잉여(Quadratic Non-Residue, NQR)"라고 한다. |
예제 1. p = 7, 원소 { 1, 2, 3, 4, 5, 6 } 일 때, 이차 잉여(QR) 및 이차 비잉여(NQR)
x = 1, 2, 3, 4, 5, 6에 대해 x2 mod 7을 계산
→ { 12, 22, 32, 42, 52, 62 } mod 7, 순서대로 계산하면 { 1, 4, 2, 2, 4, 1 }
∴ 이차잉여(QR) = { 1, 2, 4 }, 이차 비잉여(NQR) = { 3, 5, 6 }
| 정의.2 |
| 홀수 소수 p라 두고, s = (p-1)/2 일때, Sp = { x2 mod p | 0 < x ≤ s }는 법 p에 대한 모든 이차 잉여류(QR)의 집합이다. |
예제 2. p= 7, 원소 { 1, 2, 3, 4, 5, 6 } 일 때, s = 3, Sp={ 12 mod 7, 22 mod 7, 32 mod 7 } = { 1, 4, 2 } = 이차잉여(QR)
예제 3. p = 7, s = 3 그리고 x2 ≡ k (mod p) 일 때, 이차 잉여류 k 값에 대한 QR, NQR에 계산 표
| Result |
0＜ x ≤ s
|
s ＜ y ≤ p-1
|
|
k = 1
|
x = 1
|
y = 6
|
|
k = 2
|
x = 3
|
y = 4
|
|
k = 4
|
x = 2
|
y = 5
|
| 정의.3 |
| p > 2 일때, 임의의 값 k ∈Zp가 법 p에 대한 이차 잉여류인지 아닌지를 판별하는문제 S = (p-1)/2 일 때, q(k) = kS mod p 라고 정의. 만약 q(k) = 1 이면, 법 p에 대한 이차 잉여류(QR)가 된다. |
.
| 이차 잉여류 판별. |
| /* 이차 잉여를 판별 파라메터: k, p ( k: 임의의 값, p는 법) 반환값: boolean */ // isResidue function isResidue (k, p) { let re = modExp( k, Math.floor( (p-1)/2), p ); if (re == 1) { return true; // QR } else { return false; //NQR } } |
※ 이차 잉여를 판별하는 방법으로 레장드르 심볼도 참고바랍니다.
예제 4. 소수 p = 7일 때, S= (7-1)/2 =3 임의의 값 k에 대한 이차 잉여(QR), 이차 비잉여(NQR) 판별.
k = 1~6까지 대입, q(k) = k^3 mod 7.
q(1) = 13 mod 7 = 1 mod 7 = 1 → QR
q(2) = 23 mod 7 = 8 mod 7 = 1 → QR
q(3) = 33 mod 7 = 27 mod 7 = 6 → NQR
q(4) = 43 mod 7 = 64 mod 7 = 1 → QR
q(5) = 53 mod 7 = 125 mod 7 = 6 → NQR
q(6) = 63 mod 7 = 216 mod 7 = 6 → NQR
∴ k값에 대한 이차 잉여류 판별은 다음과 같다.
▷ 이차 잉여류(QR) = { 1, 2, 4 }
▷ 이차 비잉여류(NQR) = { 3, 5, 6 }