Day 142-Q1 | Pollard's Kangaroo Algorithm

問題

素数 $p$、底 $g$（$1 < g < p$）、目標値 $h$（$1 \le h < p$）、および整数区間 $[lo, hi]$（$0 \le lo \le hi < p$）が与えられる。

$g^x \equiv h \pmod p$ を満たす整数 $x$ が区間 $[lo, hi]$ 内にちょうど1つ存在することが保証されている。この $x$ を求めよ。

区間幅 $W = hi - lo$ が大きい場合、$x$ を $lo$ から順に試す $O(W)$ の全探索は間に合わない。Pollard のカンガルー法を用いて $O(\sqrt{W})$ 程度の計算量で $x$ を特定すること。

アルゴリズムの概要

ジャンプサイズの集合 $S=\{2^0,\dots,2^{k-1}\}$（$k\approx\log_2 W/2$）を用意し、$f(y)=S[y\bmod k]$ で擬似ランダムにジャンプ幅を決める
時計カンガルー: 指数 $hi$ から出発し $N$ 回ジャンプ、最終値 trap_value と総距離 trap_dist を記録
野生カンガルー: 値 $h$ から出発し trap_value に一致するまで同じ規則でジャンプ、距離 dist2 を記録
合流時、$x + \mathrm{dist2} = hi + \mathrm{trap\_dist}$ から $x=hi+\mathrm{trap\_dist}-\mathrm{dist2}$ を復元

入力形式

p g h lo hi

制約

$p$ は素数、$3 \le p < 2^{31}$

$1 < g < p$、$1 \le h < p$

$0 \le lo \le hi < p$、$hi-lo \le 10^9$

解 $x\in[lo,hi]$ がちょうど1つ存在

入出力例

入力例1

1000000007 5 372224738 0 1000000000

出力例1

123456789

概念図

ヒント（段階的開示）

ヒント1（方向性）

解の存在範囲が狭い区間 $[lo,hi]$ に限定されるとわかっている場合、その幅 $W=hi-lo$ に対して $O(\sqrt W)$ で解ける。BSGSは $O(\sqrt W)$ 空間のハッシュテーブルが必要だが、カンガルー法は $O(1)$ 空間で同等の時間計算量を達成できる。

ヒント2（アプローチ）

2匹のカンガルーは同じ「地形」（値によってジャンプ幅が決まる決定的な地形）を移動する。既知の位置から出発する時計カンガルーが罠を張り、未知の位置 $x$ から出発する野生カンガルーが同じ地形のルールに従えば、いずれ同じ値に到達し、それ以降は完全に同じ経路をたどる。合流時点の移動距離の差から $x$ を逆算する。

ヒント3（誘導）

def kangaroo(g, h, p, lo, hi):
    width = hi - lo
    k = max(1, width.bit_length() // 2)
    jumps = [1 << i for i in range(k)]
    def f(y):
        return jumps[y % k]

    N = int(4 * (width ** 0.5)) + 10
    y = pow(g, hi, p)
    dist = 0
    for _ in range(N):
        s = f(y)
        y = (y * pow(g, s, p)) % p
        dist += s
    trap_value, trap_dist = y, dist

    y = h
    dist2 = 0
    limit = trap_dist + width + 10 * int(width ** 0.5) + 100
    while dist2 <= limit:
        if y == trap_value:
            return hi + trap_dist - dist2
        s = f(y)
        y = (y * pow(g, s, p)) % p
        dist2 += s
    return None

模範解答 (Python)

import sys

def kangaroo(g, h, p, lo, hi):
    width = hi - lo
    if width == 0:
        return lo
    k = max(1, width.bit_length() // 2)
    jumps = [1 << i for i in range(k)]

    def f(y):
        return jumps[y % k]

    N = int(4 * (width ** 0.5)) + 10
    y = pow(g, hi, p)
    dist = 0
    for _ in range(N):
        s = f(y)
        y = (y * pow(g, s, p)) % p
        dist += s
    trap_value, trap_dist = y, dist

    y = h
    dist2 = 0
    limit = trap_dist + width + 10 * int(width ** 0.5) + 100
    while dist2 <= limit:
        if y == trap_value:
            x = hi + trap_dist - dist2
            if lo <= x <= hi and pow(g, x, p) == h:
                return x
        s = f(y)
        y = (y * pow(g, s, p)) % p
        dist2 += s
    return None

def main():
    p, g, h, lo, hi = map(int, sys.stdin.read().split())
    print(kangaroo(g, h, p, lo, hi))

main()

Step-by-Step 解説

1ジャンプ関数の設計
$f(y)=S[y\bmod k]$ という形で、値$y$に応じて決定的に、しかし見かけ上ランダムにジャンプ幅が決まる。同じ地形を歩く2匹は同じ値に到達すればそれ以降は完全に同じ経路をたどる。

2時計カンガルーで罠を張る
既知の位置$hi$から十分な歩数$N=O(\sqrt W)$だけ進み、最終値と距離を記録する。

3野生カンガルーで追跡
未知の$x$から出発した野生カンガルーは同じ地形を進むため、いずれtrap_valueに合流する。合流時の距離から$x$を復元する。

4計算量の直感
両者ともO(√W)歩前後で合流するため期待O(√W)（実際はモジュラー累乗込みでO(√W log p)）。BSGSと異なり空間計算量はO(1)。

5打ち切り上限
理論的には期待計算量で合流するが、無限ループを避けるためlimitで打ち切る実装上の安全策を入れる。

よくあるミス

ミス	原因	正しい書き方
ジャンプサイズを固定値1本にしてしまう	ランダム性がなく単なる線形探索と同じO(W)になる	ジャンプサイズの集合$S=\{2^0,\dots,2^{k-1}\}$を用意し値に応じて選択
時計カンガルーの歩数Nを区間幅そのもの(W)にしてしまう	罠を張る段階で全探索と同じコストがかかり高速化の意味がなくなる	$N=O(\sqrt W)$程度に抑える
合流判定を指数の比較で行おうとしてしまう	野生カンガルー側は真の指数xが未知なので比較できない	$g^{\cdot}\bmod p$の値同士を比較する
打ち切り上限limitを設定せず無限ループしてしまう	期待計算量と最悪ケースの区別を意識していない	十分大きなlimitで打ち切る
xの復元式で符号を間違える	時計・野生それぞれの移動距離の意味を混同する	時計の真の指数$hi+\mathrm{trap\_dist}$、野生の真の指数$x+\mathrm{dist2}$が等しいことから導く

次のステップ

発展: 区間幅$W$が$10^{15}$程度まで大きい場合に、$g^{2^i}\bmod p$を事前テーブル化してpow呼び出し回数を削減し実行時間を比較せよ。
発展2: 複数の目標値$h_1,\dots,h_m$が同じ$g,p,[lo,hi]$に対して与えられたとき、時計カンガルーの罠を使い回す「複数目標カンガルー法」を実装せよ。

自己評価

完全理解おおむね理解要復習

Day 142-Q1 — Pollard's Kangaroo Algorithm（区間制限離散対数のO(√幅)探索）

問題