📝
Baby-step Giant-step メモ

2025/01/31に公開
Python
 一般に
 問題設定有限巡回群 (G = \langle g \rangle) （位数 (n)）
要素 (h \in G)
典型的には 離散対数問題： g^x = h を満たす整数 x （0 \le x < n）を求める[1]

 アルゴリズムの流れステップ数の設定
m = \lceil \sqrt{n} \rceil
Baby-step

j = 0, 1, \dots, m-1 について b_j = g^j を計算し、b_j（群要素）をキーに「対応する j」をハッシュテーブルに保存する
Giant-step
（大ステップ量）g^m の逆元を g^{-m} として計算しておく

i = 0, 1, \dots, m-1 について t_i = h \cdot (g^{-m})^i を計算し、baby-step のテーブルに t_i があるか探す
もしテーブル上で t_i と一致する b_j が見つかったら t_i = g^j \Rightarrow h = g^j \cdot g^{\,m \cdot i} = g^{\,j + m \,i} より x = j + m\,i が解（離散対数）となる

!上記を高速に計算できるか（逆元が存在して大ステップ量を計算できるか等）を事前にチェックすること。

 計算量O(\sqrt{n})

 例題
 ABC186https://atcoder.jp/contests/abc186/tasks/abc186_e
有限巡回な加法群。

 解法
S + xK \equiv 0. \ \ \mod N
を解くことを考える。
まず、g=\gcd(N, S, K) として、N, S, K を g で割る。

このうえで、\gcd(K, N) \neq 1 なら K が逆元を持たない、つまり xK \equiv -S \mod N の解がないため、-1。

そうでない時、
Baby-step Giant-step
ステップ数の設定
M = \lceil \sqrt{N} \rceil
Baby-step

j = 0, 1, \dots, M-1 について、 b_j = jK を計算し、b_j をキーに対応する j をハッシュテーブルに保存する
Giant-step
（大ステップ量）-MK \mod Nを計算する

i=0, 1, \dots, M-1 について、-S+i(-MK) を計算し、Baby-stepで計算したテーブル上にあるか確認する。
このうち最小の x = j + iM が答え

サンプルコード提出
一部抜粋(Python)
def solve(N, S, K):
    g = math.gcd(math.gcd(N, S), K)
    N //= g
    S //= g
    K //= g
    if math.gcd(K, N) != 1:  # 解なし
        return -1

    M = math.ceil(math.sqrt(N))
    # Baby-step
    table = dict()
    for j in range(M):
        bj = (j * K) % N
        table[bj] = j

    # Giant-step
    g_step = (- M * K) % N
    for i in range(M):
        ti = (- S + i * g_step) % N
        if ti in table:
            return table[ti] + i * M
    return -1

 ABC270https://atcoder.jp/contests/abc270/tasks/abc270_g
最初 S で、f(X) = AX + B\mod P を何回繰り返せば G になるかという問題。

 解法先にエッジケースを処理する。
S=G のとき、変換不要なので、0。

そうでなく、A=0 のとき、B=G なら1回の変換で G になるので、1。そうでなければ恒等的に B であり G にはならないので、-1。
それ以外を Baby-step Giant-step で考える。
まず、上記の f の逆関数を考えてみる。

Y \equiv AX + B. \mod P
を変形して、

X \equiv A^{-1}(Y-B). \mod P
から、

f^{-1}(X) = A^{-1}X + c. \ \ (ここで\ c = -A^{-1}B)
とできる。
次に、これを m 回適用する関数を

f^{-m}(X) = CX + D
と書けるように、C,D を求める。k 回適用した時の値を X_k = C_k X + D_k として逆関数を1回適用すると、

f^{-1}(C_k X + D_k) = A^{-1}C_k X + A^{-1}D_k + c.
から、C_{k+1} = A^{-1}C_k,\ D_{k+1} = A^{-1}D_k + c 及び C_0 = 1,\ D_0 = 0 から、

f^{-m}(X) = C_mX + D_m
の C_m, D_m を O(m) で求められる。これで準備完了。
Baby-step Giant-step
(f^{j + mi}(S) = Gとなる最小の(j,i)を求めたい。)
ステップ数の設定
m = \lceil \sqrt{P} \rceil
Baby-step

j = 0, 1, \dots, m-1 について、 b_j = f^j(S) を計算し、b_j をキーに対応する j をハッシュテーブルに保存する。この時、同一キーに対してできるだけ小さい j を保持することに注意する。
Giant-step
（大ステップ量）上記のように f^{-m} を事前計算していると、各 i に対して順に f^{-mi}(X) を O(1) で求めることができる。

i=0, 1, \dots, m-1 について、f^{-mi}(G) を計算し、Baby-stepで計算したテーブル上にあるか確認する。
このうち最小の x = j + im が答え

サンプルコード提出
一部抜粋(Python)
def solve(P, A, B, S, G):
     if S == G:
         return 0
     if A == 0:
         if B == G:
             return 1
         else:
             return -1

     def f(X):
         return (A * X + B) % P

     # ステップ数
     M = math.ceil(math.sqrt(P))

     inv_A = pow(A, -1, P)
     c = (- B * inv_A) % P  # (-B) / A (mod P)

     C, D = 1, 0
     for _ in range(M):
         C = (inv_A * C) % P
         D = (inv_A * D + c) % P

     def f_inv_m(X):
         return (C * X + D) % P

     # Baby-step
     table = dict()
     X = S
     for j in range(M):
         if X not in table:
             table[X] = j
         X = f(X)

     # Giant-step
     crr = G
     for i in range(M):
         if crr in table:
             return i * M + table[crr]
         crr = f_inv_m(crr)

     return -1

 ABC222https://atcoder.jp/contests/abc222/tasks/abc222_g

 参考https://atcoder.jp/contests/abc270/editorial/4965
https://drken1215.hatenablog.com/entry/2020/12/20/015100

脚注
h \notin \langle g \rangle なら解がないことに注意 ↩︎
一般に

問題設定

アルゴリズムの流れ

計算量

例題

ABC186

解法

ABC270

解法

ABC222

参考

Discussion
