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