かしのブログ

競技プログラミングとか

Baby-Step Giant-Step

アルゴリズム

Baby-Step Giant-Stepアルゴリズムのまとめ

概要

巡回群上の離散対数問題を高速に解くアルゴリズム。

本記事は g^x \equiv y \mod p（pは素数）を満たすxを求める方法を考える。

アルゴリズム

ある K = \sqrt{p}と決定する

0 \le i \lt Kなるiについて、 (i, g^i)を計算する。

0 \le j \le r (K-1 \le \frac{p}{r} \lt K)なるjについて、 (j, yg^{-jK})を計算する。

解xが存在する時、jを増やしてく過程で yg^{-mK} \equiv g^nなるm, nが存在し、

  • g^n \equiv yg^{-mK}\mod p

  • g^{mK+n} \equiv y\mod p

Kの決め方

(i, g^i)の列挙をK個、 (j, yg^{-jK})の列挙を p/K個行うので、列挙数 K+p/Kを最小にする K=\sqrt{p}とする

検証

pが素数なので、 g^{mK+n}(mK+n \le p-1)は 0から(p-2)の全ての値を1回ずつとる。

g^{mK+n} \equiv y\mod pを満たす mK+nも1つだけ存在し、 g^n \equiv yg^{-mK}\mod pも1つだけ存在するので、最初に見つけたものを正解として構わない。

例

3^x \equiv 19 \mod 59

k = \sqrt{59} = 7

small step

  • 3^0 \equiv 1
  • 3^1 \equiv 3
  • 3^2 \equiv 9
  • 3^3 \equiv 27
  • 3^4 \equiv 22
  • 3^5 \equiv 7
  • 3^6 \equiv 21

giant step

3^{-1} \equiv 20

3^{-7} \equiv 15

  • 19 \times 3^{0} \equiv 19
  • 19 \times 3^{-7} \equiv 49
  • 19 \times 3^{-14} \equiv 27 \equiv 3^3

よって

3^{17} \equiv 19 \mod 59

実装

#include <iostream>
#include <math.h>
#include <map>

using namespace std;
typedef long long ll;

map<ll, ll> gn;

ll pow(ll g, ll k, ll p) {
    ll ret = 1;
    while (k) {
        if (k&1) (ret *= g) %= p;
        (g *= g) %= p;
        k >>= 1;
    }
    return ret;
}

ll inv(ll g, ll p) {
    // g^{p-2} = g^{-1}
    return pow(g, p-2, p);
}

ll babyStepGiantStep(ll p, ll g, ll y) {
    int k = sqrt(p);

    // baby step
    ll gg = 1;
    for (int i = 0; i < k; i++) {
        gn[gg] = i;
        (gg *= g) %= p;
    }

    // giant step
    ll ginv = inv(g, p);
    ll gk = pow(ginv, k, p);
    ll yg = 1;
    int r = p/k;
    for (ll j = 0; j <= r; j++) {
        ll yg = y*pow(gk, j, p)%p;
        if (gn.count(yg) != 0) {
            return  gn[yg] + j * k;
        }
    }
}

int main() {
    ll p, g, y;
    cin >> p >> g >> y;
    cout << babyStepGiantStep(p, g, y) << endl;
}

計算量

列挙にそれぞれ O(\sqrt{p})、べき乗の計算とmapの検索に O(\log p)なので全体で O(\sqrt{p}\log{p})