Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

본문 바로가기

Lagrange's Theorem

(1)

72. Discrete Square Root & Tonelli-Shanks Algorithm 이산 로그에 이어서 이산 제곱근(Discrete Square Root)에 대한 내용을 다룬다. 양의 정수

$a^2 \equiv x \pmod{m}$ 을 만족할 경우

$a$ 를

$x$ 의 이산 제곱근이라고 한다. 일반적으로

$a$ 와

$x$ 의 범위는

$m$ 미만으로 한정되며, 이 범위에서 정수

$x$ 의 이산 제곱근을 빠르게 구하는 방법이 존재한다. 일단

$\gcd(x, m) = 1$ 이라고 가정한다. 먼저

$m$ 이 소수인 경우 이산 제곱근을 구하는 방법을 알아본다.

$m = 2$ 라면

$x$ 의 이산 제곱근이

$x$ 하나라는 것은 쉽게 알 수 있으므로

$m$ 이 홀수 소수인 경우만 고려하면 된다. 먼저 이산 제곱근이 존재하지 않는 경우를 처리해야 하는데, 페르마의 소정리에 의해 $a^{m-1}..

티스토리툴바