이차잉여
이차잉여 / 이차비잉여 (Quadratic Residue / Quadratic Non-Residue) 의 의미는 다음과 같습니다.
$3$ 이상의 자연수 $n$과, $n$과 서로소 인 $a$에 대하여 $x$에 대한 이차합동방정식
$$ x^{2} \equiv a \pmod{n} $$ 의 해가 존재하면 $a$를 법 $n$에 대한 이차잉여, 해가 존재하지 않으면 $a$를 법 $n$에 대한 이차비잉여라고 한다.
통상적으로 $n$이 소수 $p$일 때의 이차합동방정식을 더욱 더 많이 따집니다.
해의 "존재성"은 이차잉여이고, 그 해가 실제로 무엇인가는 이산 제곱근 문제가 됩니다.
소수 $p$에 대하여 $p \equiv 3 \pmod{4}$이면 $x^{2} \equiv a \pmod{p}$의 해는 $x \equiv \pm a^{\frac{p + 1}{4}} \pmod{p}$ 임이 알려져있고,
$p \equiv 5 \pmod{8}$이면 $x^{2} \equiv a \pmod{p}$의 해는 $x \equiv \pm (2a) (4a)^{\frac{p - 5}{8}} \pmod{p}$임이 알려져 있습니다.
$p \equiv 1 \pmod{8}$이면 알려진 명시적인 해는 아직 없습니다. 따라서 이 경우의 이산 제곱근은 토넬리-섕크스 알고리즘 등으로 해를 찾아야 합니다.
$n$이 소수 $p$이면 르장드르 기호 를 통해서도 많이 표현합니다.
르장드르 기호에서 $n$이 홀수인 것까지 확장한 경우에는 야코비 기호 를 통해서 표현합니다.