이산 제곱근 (Discrete Square Root / Tonelli-Shanks)

정의

이산 제곱근 (Discrete Square Root) 은 소수 p 에 대해 x^2 ≡ a (mod p) 를 만족하는 x 를 찾는 문제. a 가 이차잉여 (quadratic residue) 이면 해가 존재하며, Tonelli-Shanks 알고리즘 (1970, Daniel Shanks) 이 일반적인 소수 p 에 대해 O(log^2 p) 시간에 해를 구한다. p ≡ 3 (mod 4) 일 때는 x = ±a^{(p+1)/4} 로 단순화.

문제 상황과 동기

x^2 ≡ a (mod p) 에서 x 를 구하라. p 는 홀수 소수.

• naive: x = 0..p-1 을 순회. O(p). p=10^9 면 불가능.
• p ≡ 3 (mod 4): x = ±a^{(p+1)/4}. 거듭제곱 O(log p).
• 일반 p (p ≡ 1 mod 4): Tonelli-Shanks. O(log^2 p).

핵심 통찰: 합성곱(quadratic residue) 구조를 이용해 p-1 = s·2^e 로 분해, 반복적으로 위수를 줄임.

시각화

핵심 아이디어

p-1 = s·2^e (s: 홀수). Tonelli-Shanks 는 다음 invariant 를 유지한다.

찾고자 하는 값: n (a = n)
p-1 = s·2^e

초기:
  x = n^{(s+1)/2}   # 첫 추정값
  b = n^s
  g = z^s           # z: 임의의 비제곱수
  r = e

반복:
  1. b^(2^m) ≡ 1 (mod p) 인 최소 m (0 < m ≤ r) 찾기
  2. m=0 이면 종료, x 가 답
  3. 아니면 x, b, g, r 갱신

특수 경우: p ≡ 3 (mod 4) 이면 x = ±n^{(p+1)/4} mod p.

알고리즘

tonelli_shanks(n, p):
    if n % p == 0: return 0
    if p % 4 == 3: return n^((p+1)/4) % p

    s, e = factorization of p-1 as s·2^e
    z = 2
    while z^((p-1)/2) != p-1 mod p: z += 1  # 비제곱수 찾기

    x = n^((s+1)/2) % p
    b = n^s % p
    g = z^s % p
    r = e

    while true:
        m = find_min_m(b, p, r)
        if m == 0: return x
        x = x · g^(2^(r-m-1)) % p
        b = b · g^(2^(r-m)) % p
        g = g^(2^(r-m)) % p
        r = m

구현

// Tonelli-Shanks: sqrt(n) mod p, O(log^2 p)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
ll modpow(ll a, ll b, ll m) {
  ll r = 1;
  while (b) { if (b & 1) r = r * a % m; a = a * a % m; b >>= 1; }
  return r;
}
​
ll tonelli_shanks(ll n, ll p) {
  if (n == 0) return 0;
  if (p % 4 == 3) return modpow(n, (p + 1) / 4, p);
  ll s = p - 1, e = 0;
  while (s % 2 == 0) s /= 2, e++;
  ll z = 2;
  while (modpow(z, (p - 1) / 2, p) != p - 1) z++;
  ll x = modpow(n, (s + 1) / 2, p);
  ll b = modpow(n, s, p);
  ll g = modpow(z, s, p);
  ll r = e;
  while (true) {
      ll m = 0, tmp = b;
      while (m < r && tmp != 1) tmp = tmp * tmp % p, m++;
      if (m == 0) return x;
      ll g_pow = modpow(g, 1LL << (r - m - 1), p);
      x = x * g_pow % p;
      g = g_pow * g_pow % p;
      b = b * g % p;
      r = m;
  }
}
​
int main() {
  ll n, p; cin >> n >> p;
  ll x = tonelli_shanks(n, p);
  ll other = p - x;
  if (x == 0 || x == other) cout << x;
  else cout << min(x, other) << " " << max(x, other);
  return 0;
}

# Tonelli-Shanks: sqrt(n) mod p
def tonelli_shanks(n, p):
  if n == 0: return 0
  if p % 4 == 3: return pow(n, (p + 1) // 4, p)
  s, e = p - 1, 0
  while s % 2 == 0: s //= 2; e += 1
  z = 2
  while pow(z, (p - 1) // 2, p) != p - 1: z += 1
  x = pow(n, (s + 1) // 2, p)
  b = pow(n, s, p)
  g = pow(z, s, p)
  r = e
  while True:
      m, cur = 0, b
      while m < r and cur != 1:
          cur = cur * cur % p
          m += 1
      if m == 0: return x
      g_pow = pow(g, 1 << (r - m - 1), p)
      x = x * g_pow % p
      g = g_pow * g_pow % p
      b = b * g % p
      r = m
​
import sys
n, p = map(int, sys.stdin.readline().split())
x = tonelli_shanks(n, p)
other = p - x
if x == 0 or x == other: print(x)
else: print(min(x, other), max(x, other))

8 19

6 13

8 17

5 12

0 17

0

복잡도

변형 / 활용

Cipolla 알고리즘

Tonelli-Shanks 와 달리 비제곱수의 제곱근을 F_p[x]/(x^2 - a) 에서 직접 계산. O(log p). 구현은 더 짧지만, F_p^2 체 연산 필요.

합성수 mod

합성수 mod m 에서 제곱근은 인수분해와 동등한 난이도. CRT 로 각 소인수에 대한 해 결합.

응용

타원곡선 좌표 찾기, Rabin 암호 복호화, Quadratic sieve 체 단계.

함정

1. p 가 소수가 아닌 경우

Tonelli-Shanks 는 소수 p 에 대해서만 동작. 합성수 mod 는 인수분해 필요. 소수 판별 없이 들어오면 잘못된 결과.

2. 비제곱수 z 탐색

확률적 (무작위 시도). 기대 2회 시도. 최악 O(p) 가능하나 실용적.

3. 해가 없는 경우

a^((p-1)/2) ≠ 1 mod p 이면 이차잉여가 아님. Euler criterion 으로 미리 확인.

BOJ 연습 문제

참고

• 이산 로그 (BSGS)
• 모듈러 역원
• 오일러 기준
• 분할 정복을 이용한 거듭제곱
• 중국인의 나머지 정리