ホーム > libalgo

離散対数問題

概要

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

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

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

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

計算量

$O(\sqrt m \log m)$

使い方

modlog(x,y,m)
$x^k = y$ を満たす $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;
}