Lagrange's Theorem (1) 썸네일형 리스트형 72. Discrete Square Root & Tonelli-Shanks Algorithm 이산 로그에 이어서 이산 제곱근(Discrete Square Root)에 대한 내용을 다룬다. 양의 정수 $m$에 대해 $a^2 \equiv x \pmod{m}$을 만족할 경우 $a$를 $x$의 이산 제곱근이라고 한다. 일반적으로 $a$와 $x$의 범위는 $0$ 이상 $m$ 미만으로 한정되며, 이 범위에서 정수 $x$의 이산 제곱근을 빠르게 구하는 방법이 존재한다. 일단 $\gcd(x, m) = 1$이라고 가정한다. 먼저 $m$이 소수인 경우 이산 제곱근을 구하는 방법을 알아본다. $m = 2$라면 $x$의 이산 제곱근이 $x$ 하나라는 것은 쉽게 알 수 있으므로 $m$이 홀수 소수인 경우만 고려하면 된다. 먼저 이산 제곱근이 존재하지 않는 경우를 처리해야 하는데, 페르마의 소정리에 의해 $a^{m-1}.. 이전 1 다음
