離散対数問題

概要

$x^k = y \mod m$ を満たす $k$ を求める．

以下に出てくる式は全て $\mathrm{mod} \ m$ で考えているものとする．

$x^0, x^1, x^2, \ldots$ には 長さが $m$ 以下の周期がある．その中に $y$ は含まれるか，含まれるなら何番目かが分かればいい． 周期が $m$ 以下なので，もし $y$ が含まれるとき， $x^H, x^{2H}, \ldots, x^{H \times H} \ (H = \lceil \sqrt m \rceil)$ を前から順に見ると $yx^0, yx^1, yx^2, \ldots, yx^{H-1}$ のうちどれかをいつか踏む． $yx^0, yx^1, yx^2, \ldots, yx^{H-1}$ の方を事前に計算しておけば， 踏んだ場所から先頭である $y$ およびそのインデックス ($=k$) が分かる． $y$ から1ずつ進む方を baby-step, 先頭から $H$ ずつ進む方を giant-step と呼ぶので， このアルゴリズムは Baby-step Giane-Step アルゴリズムと呼ばれる．

いわゆる平方分割であり，離散対数問題に限らずたまに使える．

計算量

$O(\sqrt m \log m)$

使い方

modlog(x,y)

$x^k = y \mod m$ を満たす $k$ を求める

実装

ll modlog(ll x, ll y) {
    ll H = sqrt(MOD) + 1;
    static std::pair<ll, ll> baby[100010];
    for (ll b = 0, xby = y; b < H; b++, xby = (xby * x) % MOD) {
        baby[b] = std::make_pair(xby, b);
    }
    std::sort(baby, baby + H);
    ll xH = 1;
    for (int i = 0; i < H; ++i) {
        xH = (xH * x) % MOD;
    }
    for (ll a = 1, xaH = xH; a <= H; a++, xaH = (xaH * xH) % MOD) {
        auto it = std::lower_bound(baby, baby + H, std::make_pair(xaH + 1, 0LL));
        if (it == baby) continue;
        it--;
        if (it->first == xaH) return a * H - it->second;
    }
    return -1;
}