Euler's Criterion: 이차잉여 판정

Euler's Criterion, 이차잉여 판정, quadratic residue

정의

홀소수 p 에 대해 a 가 mod p 에서 이차잉여 (quadratic residue) 인지 판정:

a^\{(p-1)/2\} \equiv \begin\{cases\} 1 & \text\{a is QR\} \\ -1 & \text\{a is NR\} \end\{cases\} \pmod\{p\}

Legendre symbol (a/p) 는 위 결과 (또는 0 if p|a).

왜 성립하는가

Fermat’s Little Theorem: a^(p-1) ≡ 1 (mod p). 그러면 (a^((p-1)/2))² ≡ 1, 즉 a^((p-1)/2) ≡ ±1.

만약 a ≡ b² 이면 a^((p-1)/2) ≡ b^(p-1) ≡ 1.

응용

• Tonelli-Shanks: sqrt mod p 계산 (QR 여부 판정에 사용)
• Solovay-Strassen 소수 판정

참고

• Fermat’s Little Theorem
• Tonelli-Shanks
• Quadratic Residue