이산 제곱근

이산 제곱근 (Discrete Square Root) 의 정의는 다음과 같습니다.

$x$에 대한 합동방정식 $x^{2} \equiv a \pmod{n}$의 해 $x$를 이산 제곱근이라 한다.

생긴 모양에서 알 수 있듯이 이차잉여 와 관련된 개념입니다.
$n$이 특정 모양의 소수 일 때 편하게 구하는 방법이 알려져있습니다.
소수 $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}$임이 알려져 있습니다.