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} \equiv 1 \pmod{m}$이므로 $(a^2)^{\frac{m-1}{2}} \equiv 1 \pmod{m}$이다. 따라서 $x$가 이산 제곱근을 갖는 경우 $x^{\frac{m-1}{2}} \equiv 1 \pmod{m}$이고, 그 역도 성립하므로 이 값을 확인하면 $x$의 이산 제곱근이 존재하는지를 알 수 있다.

 

$x$의 이산 제곱근이 존재하고 $m$이 $4k+3$ 꼴의 소수일 경우, $\frac{m+1}{2}$가 짝수이므로 앞에 나온 식을 변형해서 $a$를 다음과 같이 $x$와 $m$에 관한 식으로 나타낼 수 있다.

$$x^\frac{m-1}{2} \equiv 1 \pmod{m}$$

$$x^\frac{m+1}{2} \equiv x \pmod{m}$$

$$(x^\frac{m+1}{4})^2 \equiv a^2 \pmod{m}$$

$$x^\frac{m+1}{4} \equiv a \pmod{m}$$

세 번째 식에서 네 번째 식으로 넘어갈 때 양변의 제곱을 없애면서 절댓값 기호를 붙이지 않은 이유는 값들의 범위를 $0$ 이상 $m$ 미만으로 한정했기 때문이다. 이산 제곱근도 일반적인 제곱근과 마찬가지로 $a$가 $x$의 이산 제곱근이면 $m-a$도 $x$의 이산 제곱근이기 때문에 여기서는 절댓값에 신경쓰지 않기로 한다.

 

어쨌든 $m$이 $4k+3$ 꼴의 소수인 경우 $x$의 이산 제곱근은 $x^\frac{m+1}{4} \,\bmod\, m$과 $(m-x^\frac{m+1}{4}) \,\bmod\, m$이므로 간단한 거듭제곱으로 이산 제곱근을 구할 수 있다. $m$이 $4k+1$ 꼴의 소수인 경우 $\frac{m+1}{4}$가 정수가 아니므로 이 방법을 사용할 수 없는데, 이때 이산 제곱근을 구하는 방법이 Tonelli-Shanks Algorithm이다. 이 알고리즘은 $\Theta(\text{lg}^2m)$ 시간에 $x$의 이산 제곱근을 찾아내며 다음과 같은 방법으로 동작한다.

$m-1 = w \cdot 2^t$를 만족하는 홀수 $w$와 음이 아닌 정수 $t$를 구하고, 이산 제곱근을 갖지 않는 정수 $z$를 아무거나 하나 찾는다. 이산 제곱근을 갖지 않는 정수의 개수 역시 많으므로 아무 수나 골라서 이산 제곱근이 존재하는지 판별하는 과정을 반복하면 $z$를 빠르게 찾을 수 있다.

$w, t, z$를 구했다면 $c = z^w, s = x^w, y = x^{\frac{w+1}{2}}$이라고 한다. (각각의 수에는 계속 $\bmod\, m$ 연산을 수행한다.) 이때 $c^{2^t} \equiv s^{2^t} \equiv 1 \pmod{m}$이고 $y^2 \equiv xs \pmod{m}$이다.

이제 $s$가 $1$이 될 때까지 다음 과정을 반복한다.

• $s^{2^{t'}} \equiv 1 \pmod{m}$를 만족하는 가장 작은 양의 정수 $t'$을 찾는다. 이 값은 항상 $t$보다 작다.
• $v = c^{2^{t-t'-1}}$로 두고 $t$ ← $t'$, $c$ ← $v^2$, $s$ ← $sv^2$, $y$ ← $yv$로 값을 바꾼다.

$t$의 초기값은 $\text{lg }m$ 이하이고 반복 과정에서 $t$가 계속 감소하므로 반복 횟수는 $\text{lg }m$보다 크지 않다. 또한 각각의 반복 과정에서 $y^2 \equiv xs \pmod{m}$인 상태가 계속 유지되므로 반복이 끝나면 $y^2 \equiv x \pmod{m}$이며 $y$와 $m-y$가 $x$의 이산 제곱근이 된다.

 

$m$의 형태에 따라 이산 제곱근을 더 간단하게 구하는 방법에 대해서는 아래의 파일을 참고하면 좋다.

Discrete Sqrt.pdf

0.51MB

$m$이 홀수 소수인 경우 $x$의 이산 제곱근은 항상 $0$개 또는 $2$개이다. 이를 Lagrange's Theorem이라고 하며 자세한 내용은 참고 링크에서 확인할 수 있다.

---

다음으로 $m$이 $p^k$ 꼴인 경우 ($p$는 소수) 이산 제곱근을 구하는 방법에 대해 알아본다. 앞에서 $k = 1$인 경우 이산 제곱근을 구하는 방법을 확인했으므로 $m = p^k$인 경우의 이산 제곱근을 $m = p^{k+1}$인 경우로 확장하는 방법을 찾으면 된다. 먼저 $p = 2$인 경우, $k = 2$일 때 $1$의 이산 제곱근은 1이고, $k = 3$일 때 $1$의 이산 제곱근은 $1, 3, 5, 7$이고 $3, 5, 7$의 이산 제곱근은 존재하지 않는다. $k \ge 4$인 경우는 다음과 같은 방법을 재귀적으로 적용하면 이산 제곱근을 구할 수 있다.

• $x \,\bmod\, 8 = 1$일 때 $x$의 이산 제곱근은 $4$개이며 그 외의 경우 이산 제곱근이 존재하지 않는다.
• $a^2 \equiv x \pmod{2^k}$일 때 $a, -a, a+2^k, -a+2^k$는 모두 $x$의 이산 제곱근이다.
• $a^2 \equiv x \pmod{2^k}$일 때 $a^2$과 $(a+2^{k-1})^2$을 $2^{k+1}$로 나눈 나머지는 $x, x+2^k$ 중 하나이며 서로 다르다.

$p \ge 3$인 경우 $a^2 \equiv x \pmod{p^k}$라고 하면 $(a+tp^k)^2 \equiv x \pmod{p^{k+1}}$이고 $0 \le t < p$인 정수 $t$가 존재한다. 이 식을 전개한 다음 다음과 같이 변형할 수 있다.

$$(a+tp^k)^2 \equiv x \pmod{p^{k+1}}$$

$$a^2+2atp^k+x^2p^{2k} \equiv x \pmod{p^{k+1}}$$

$$a^2+2atp^k \equiv x \pmod{p^{k+1}}$$

$$2atp^k \equiv x-a^2 \pmod{p^{k+1}}$$

이때 $a^2 \equiv x \pmod{p^k}$이므로 $x-a^2$은 $p^k$의 배수이다. 또한 $2a$와 $p$가 서로소이므로 식을 다시 아래와 같이 변형할 수 있다.

$$2at \equiv \frac{x-a^2}{p^k} \pmod{p}$$

$$t \equiv \frac{x-a^2}{p^k} \cdot (2a)^{-1} \pmod{p}$$

$$t = \frac{x-a^2}{p^k} \cdot (2a)^{p-2} \,\bmod\, p$$

이 방법을 재귀적으로 적용하면 $m$이 $p^k$인 경우의 이산 제곱근을 구할 수 있다. 이를 Hensel's (Lifting) Lemma라고 한다. 더 자세한 내용은 참고 링크에서 확인할 수 있다.

---

이제 $\gcd(x, m)$이 $1$이 아닌 경우를 살펴보자. 이 경우는 다음 사실을 바탕으로 재귀적으로 이산 제곱근을 구할 수 있다.

• $a^2 \equiv x \pmod{p^k}$일 때 $(ap)^2 = a^2p^2 \equiv xp^2 \pmod{p^{k+2}}$이며 $x \ne 0$이면 그 역도 성립한다.
• $a^2 \equiv (a+p^{\lceil \frac{k}{2} \rceil})^2 \pmod{p^k}$
• $x = w \cdot p^t$이고 $w \,\bmod\, p \ne 0$일 때 $t < k$이고 $t$가 홀수이면 $x$의 이산 제곱근은 존재하지 않는다.

마지막으로 $m$의 서로 다른 소인수가 $2$개 이상인 경우의 이산 제곱근을 구하는 방법이 남았는데, 이때는 $m$의 각 소인수에 대한 이산 제곱근을 구한 다음 중국인의 나머지 정리를 이용하면 이산 제곱근을 구할 수 있다.

 

[참고 링크]

 

Tonelli–Shanks Algorithm

Lagrange's Theorem

Hensel's Lemma

블로그

 

[연습문제]

 

BOJ 17603. Factorization (Diamond V)

주어진 식을 변형하면 ${a_1}^2-4a_0 \equiv (b_0-b_1)^2 \pmod{p}$이다. Tonelli-Shanks Algorithm으로 $({a_1}^2-4a_0) \,\bmod\, p$의 이산 제곱근을 구하면 $b_0-b_1$의 값이 나오므로 간단한 연립방정식을 풀면 $b_0$과 $b_1$을 구할 수 있다.

 

→ solved.ac tag: discrete_sqrt