이산 로그 (Discrete Logarithm)

정의

이산 로그 (Discrete Logarithm) 는 군 G 에서 a^x ≡ b (mod m) 를 만족하는 최소 음이 아닌 정수 x 를 찾는 문제. 실수 로그와 달리, mod 연산 아래에서의 역연산은 어렵다 (trapdoor function). Baby-step giant-step (BSGS) 알고리즘은 x 를 O(√m) 시간에 찾는 meet-in-the-middle 기법으로, Daniel Shanks 가 1971년 고안.

문제 상황과 동기

a^x ≡ b (mod m) 에서 x 를 구하라. m ≤ 10^9, 다중 쿼리.

• naive: x = 0..m-1 을 순회. O(m). m=10^9 면 불가능.
• BSGS: O(√m) 시간 + O(√m) 공간. m=10^9 면 약 31623 단계.

핵심 통찰: x 를 i·m + j 로 분할, baby step 으로 j 를 테이블에 저장, giant step 으로 i 를 찾는다.

시각화

핵심 아이디어

x = i·m + j (0 ≤ i, j < m, m = ⌈√φ(m)⌉ 또는 ⌈√m⌉).

a^(i·m + j) ≡ b (mod m)
→ a^j ≡ b · (a^(-m))^i (mod m)

1. Baby step: j = 0..m-1 에 대해 a^j mod m 을 hash map 에 저장.
2. Giant step: i = 0..m-1 에 대해 b · (a^(-m))^i mod m 이 hash map 에 있는지 확인.
3. 일치하면 x = i·m + j 반환.

m 이 1이 아닌 경우 a 와 m 이 서로소여야 a^(-1) 존재. 서로소가 아니면 일반화된 알고리즘 필요.

알고리즘

discrete_log(a, b, m):
    a = a mod m, b = b mod m
    if b == 1: return 0

    m_sqrt = ceil(sqrt(m))
    cur = 1
    table = {}
    for j in 0..m_sqrt-1:      # baby step
        if cur not in table:
            table[cur] = j
        cur = cur * a mod m

    factor = a^(-m_sqrt) mod m  # modular inverse
    cur = b
    for i in 0..m_sqrt-1:       # giant step
        if cur in table:
            return i * m_sqrt + table[cur]
        cur = cur * factor mod m

    return -1   # not found

구현

// Baby-step giant-step: a^x = b (mod m), O(sqrt(m))
#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 discrete_log(ll a, ll b, ll m) {
  a %= m; b %= m;
  if (b == 1) return 0;
  ll n = (ll)sqrt(m) + 1;
  unordered_map<ll, ll> baby;
  ll cur = 1;
  for (ll j = 0; j < n; j++) {
      if (!baby.count(cur)) baby[cur] = j;
      cur = cur * a % m;
  }
  ll factor = modpow(a, m - 1 - (n - 1), m);
  if (factor < 0) factor += m;
  cur = b;
  for (ll i = 0; i < n; i++) {
      if (baby.count(cur)) return i * n + baby[cur];
      cur = cur * factor % m;
  }
  return -1;
}
​
int main() {
  ll a, b, m; cin >> a >> b >> m;
  ll x = discrete_log(a, b, m);
  if (x == -1) cout << "Not found\n";
  else cout << a << "^" << x << " mod " << m << " = " << b << "\n";
  return 0;
}

# Baby-step giant-step
import math
​
def discrete_log(a, b, m):
  a %= m; b %= m
  if b == 1: return 0
  n = int(math.isqrt(m)) + 1
  baby = {}
  cur = 1
  for j in range(n):
      if cur not in baby: baby[cur] = j
      cur = cur * a % m
  factor = pow(a, -n, m)  # Python 3.8+: modular inverse
  cur = b
  for i in range(n):
      if cur in baby: return i * n + baby[cur]
      cur = cur * factor % m
  return -1
​
import sys
a, b, m = map(int, sys.stdin.readline().split())
x = discrete_log(a, b, m)
if x == -1: print("Not found")
else: print(f"{a}^{x} mod {m} = {b}")

2 3 5

2^3 mod 5 = 3

7 15 1000000007

7^1026762786 mod 1000000007 = 15

복잡도

변형

함정

1. a 와 m 이 서로소가 아닌 경우

a 와 m 이 gcd > 1 이면 modular inverse 가 존재하지 않아 BSGS 를 바로 쓸 수 없음. 이 경우 일반화된 이산 로그 (Pohlig-Hellman, 또는 확장 BSGS) 필요.

2. mod 가 1인 경우

m = 1 이면 모든 수가 0 ≡ 0. 아무 x 나 답. 특수 처리.

3. 해가 없는 경우

BSGS 가 -1 을 반환하면 해가 없음. 단, 순환군이 아닌 mod 에서는 실제 해가 있어도 BSGS 가 찾지 못할 수 있음.

4. Hash table 충돌

map/unordered_map 충돌로 O(√m) 보다 느려질 수 있음. C++ unordered_map 은 최악 O(n). 충돌 방지를 위해 map (RB-tree, O(log √m)) 사용도 고려.

BOJ 연습 문제

참고

• 분할 정복을 이용한 거듭제곱
• 확장 유클리드 호제법 (modular inverse)
• 모듈러 역원
• 중국인의 나머지 정리 (Pohlig-Hellman)