이산 로그

문제

소수 \(p\)(또는 일반 법 \(m\))에서

$$ a^x \equiv b \pmod{p} $$

를 만족하는 가장 작은 비음 정수 \(x\)를 찾는 것이 이산 로그(discrete logarithm) 문제다. 지수 \(x\)가 미지수라는 점에서 거듭제곱(\(a^x\) 계산)과 정반대 방향이다.

이 문제의 어려움 이 Diffie–Hellman, ElGamal 등 공개키 암호의 기반이다. 하지만 경시 범위의 \(p\)(\(\le 10^{18}\) 또는 그 이하)에서는 \(O(\sqrt p)\) 알고리즘으로 풀 수 있다.

Baby-step Giant-step (BSGS)

\(x = i \cdot n - j\)로 쓰자. 여기서 \(n = \lceil \sqrt{p} \rceil\), \(0 \le j < n\), \(1 \le i \le n\). 그러면

$$ a^{in - j} \equiv b \;\Longleftrightarrow\; a^{in} \equiv b \cdot a^{j} \pmod p. $$

(또는 \(x = in + j\) 변형도 흔하다. 부호 규약만 일관되면 된다.)

전략:

1. Baby steps: \(j = 0, 1, \dots, n-1\)에 대해 \(b \cdot a^j \bmod p\)를 모두 해시맵에 저장.
2. Giant steps: \(i = 1, 2, \dots, n\)에 대해 \(a^{in} \bmod p\)를 계산하며, 해시맵에 같은 값이 있으면 매칭. 그때 \(x = in - j\).

각 단계가 \(O(\sqrt p)\), 맵 조회 \(O(1)\) 평균. 총 \(O(\sqrt p)\) 시간/공간.

정당성

답 \(x\)가 존재하면 \(0 \le x < \text{ord}(a) \le p-1\)이므로 \(x = in - j\) 형태로 \(i \in [1, n], j \in [0, n)\) 범위에서 반드시 표현된다(\(n^2 \ge p\)). 따라서 두 단계의 어딘가에서 충돌이 일어난다. 가장 작은 \(x\)는 \(i\)를 오름차순으로 보며 첫 매칭에서 얻는다(같은 \(i\) 내에선 큰 \(j\) = 작은 \(x\) 주의 — 규약에 맞게 정리).

\(\gcd(a, p) \ne 1\) 일반화

\(a\)와 법 \(m\)이 서로소가 아니면 \(a\)가 가역이 아니라 위 변형이 깨진다. 공통 인수를 단계적으로 제거한다.

반복: \(g = \gcd(a, m)\). \(g \nmid b\)이고 \(b \ne 1\)이면 해 없음. \(g \mid b\)이면

$$ \frac{a}{g} \cdot a^{x-1} \equiv \frac{b}{g} \pmod{\frac{m}{g}} $$

로 줄이고 \(x\)를 1 줄인 부분 문제를 푼다. 이 "제거 후 BSGS"가 확장 BSGS.

복잡도

지수가 매우 큰 군(암호 수준)에선 비현실적이지만, 경시 \(m\)에선 충분히 빠르다. 다음 강의에서 구현과 확장.

기본 BSGS (gcd(a, m) = 1 가정)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mulmod(ll a, ll b, ll m){ return (__int128)a*b%m; }
ll powmod(ll a, ll e, ll m){
    ll r=1%m; a%=m;
    while(e){ if(e&1) r=mulmod(r,a,m); a=mulmod(a,a,m); e>>=1; }
    return r;
}

// 최소 x>=0 with a^x ≡ b (mod m), gcd(a,m)=1; 없으면 -1
ll bsgs(ll a, ll b, ll m){
    a%=m; b%=m;
    if(m==1) return 0;
    if(b==1%m) return 0;
    ll n=(ll)ceil(sqrt((double)m));
    unordered_map<ll,ll> table;
    table.reserve(n*2);
    ll cur=b;
    for(ll j=0; j<n; j++){           // baby: b * a^j
        table[cur]=j;                // 큰 j가 덮어써도 최소 x 위해 i 우선
        cur=mulmod(cur,a,m);
    }
    ll an=powmod(a,n,m);             // a^n
    cur=1;
    for(ll i=1; i<=n; i++){          // giant: a^(i n)
        cur=mulmod(cur,an,m);
        auto it=table.find(cur);
        if(it!=table.end()){
            ll x=i*n - it->second;   // x = i n - j
            if(x>=0) return x;
        }
    }
    return -1;
}

x = in - j에서 같은 충돌 값에 여러 \(j\)가 있으면 작은 \(i\) 먼저 보므로, 첫 매칭이 최소 \(x\)다(같은 \(i\) 내 큰 \(j\)는 맵에 덮어쓰여 있어 자연히 처리되지만, 엄밀히 최소가 필요하면 맵에 최소 \(j\)만 저장하도록 if(!table.count(cur)) table[cur]=j;로 바꾼다 — 이 경우 큰 \(j\)=작은 \(x\)이므로 큰 \(j\)를 보존해야 함에 주의).

규약 정리: 최소 \(x\)를 원하면 baby에서 마지막 \(j\)(가장 큰)를 보존(table[cur]=j; 그대로 덮어쓰기)하고 giant에서 가장 작은 \(i\)를 본다. 위 코드가 그 규약이다.

확장 BSGS (gcd(a, m) ≠ 1)

ll exbsgs(ll a, ll b, ll m){
    a%=m; b%=m;
    if(b==1%m || m==1) return 0;
    ll cnt=0, d, ad=1;
    while((d=__gcd(a,m))>1){
        if(b%d) return -1;           // 해 없음
        b/=d; m/=d; cnt++;
        ad=mulmod(ad, a/d, m);
        if(ad==b%m) return cnt;      // a^cnt 가 곧 답
    }
    // 이제 gcd(a, m)=1; ad * a^y ≡ b  →  a^y ≡ b * ad^{-1}
    ll inv=powmod(ad, /*phi 없이*/ 0, m); // 아래 확장유클리드로 역원
    // ad^{-1} mod m
    function<ll(ll,ll,ll&,ll&)> ext=[&](ll A,ll B,ll&x,ll&y)->ll{
        if(!B){ x=1; y=0; return A; }
        ll x1,y1,g=ext(B,A%B,x1,y1);
        x=y1; y=x1-(A/B)*y1; return g;
    };
    ll x,y; ext(ad%m, m, x, y);
    ll adinv=((x%m)+m)%m;
    ll bb=mulmod(b, adinv, m);
    ll r=bsgs(a, bb, m);
    return r==-1? -1 : r+cnt;
}

while에서 공통 인수 \(d\)를 단계적으로 제거하며 cnt만큼 지수를 당겨 둔 뒤, 서로소가 된 부분 문제를 일반 BSGS로 푼다. 답은 r + cnt.

검증

• \(2^x \equiv 1 \pmod{1000000007}\) → \(x=0\)(또는 위수).
• 원시근 \(g\)에 대해 \(g^k\)를 만들어 다시 \(k\)를 복원하는 round-trip.
• gcd 비서로소 케이스: \(4^x \equiv 8 \pmod{12}\) 같은 손계산 예제.

함정과 확장

• 곱셈 오버플로: __int128로 mulmod.
• unordered_map 충돌 공격 회피: 사용자 해시 또는 정렬 + 이분탐색.
• 위수가 작을 때 최소 \(x\) 규약을 정확히. 음수 \(x\) 방지(x>=0 확인).
• 합성수 법, 비서로소는 반드시 exBSGS.

복잡도 \(O(\sqrt m \log m)\). \(m \le 10^{12}\) 정도까지 실용적이며, 군의 위수가 작으면 더 빠르다.