ベビーステップ・ジャイアントステップ法

$m = ⌈ N ⌉$ （ $N$ は $g$ の位数）として $g^{j}$ （ $0 \leq j < m$ ）の表を作り、 $h (g^{- m})^{i}$ と照合して $x = im + j$ を見つけ、 $g^{x} \equiv h (mod p)$ の離散対数を小さな $p$ で求められる

前提

この技能までの道筋（28 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
n 進法（数学A 整数の性質）
繰り返し二乗法によるべき剰余（大学数学暗号理論）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
ユークリッドの互除法（数学A 整数の性質）
1 次不定方程式の整数解（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）
群の位数と元の位数（大学数学代数学）
有限アーベル群の構造と部分群の個数（大学数学代数学）
剰余類環の単元群とオイラー関数（大学数学代数学）

説明

ベビーステップ・ジャイアントステップ法（BSGS 法）は、素数 $p$ と整数 $g, h$ が与えられたとき、 $g^{x} \equiv h (mod p)$ を満たす指数 $x$ （離散対数）を求める方法です。 $g$ の位数を $N$ とすると、 $x = 0, 1, 2, \dots$ と順に試す方法では最大で約 $N$ 回の掛け算が必要です。BSGS 法ではこれが約 $2 N$ 回で済みます。暗号（ディフィー・ヘルマン鍵共有など）の安全性を考えるときの基本的な攻撃法でもあり、小さな $p$ なら手計算で離散対数を求められます。

なぜそうしてよいのか

$g$ の位数を $N$ とし、 $m = ⌈ N ⌉$ とおきます。 $m^{2} \geq N$ なので、 $0 \leq x < N$ の整数 $x$ はどれも $x$ を $m$ で割った商 $i$ と余り $j$ を使って $x = im + j$ （ $0 \leq i < m, 0 \leq j < m$ ）と書けます。商 $i$ も $m$ 未満に収まるのは、 $x < N \leq m^{2}$ だからです。

この $x$ について、 $g^{x} \equiv h$ は $g^{im} g^{j} \equiv h$ と同じです。両辺に $g^{- im} = (g^{- m})^{i}$ を掛けると $g^{j} \equiv h (g^{- m})^{i} (mod p)$ となります。 $g cd (g, p) = 1$ なので $g^{- m}$ は法 $p$ での逆元として存在します。そこで、左辺の候補 $g^{0}, g^{1}, \dots, g^{m - 1}$ を先に表にしておきます（小さな歩幅なのでベビーステップ）。次に右辺 $h, h g^{- m}, h g^{- 2 m}, \dots$ を順に作って表と照合します（ $m$ ずつの大きな歩幅なのでジャイアントステップ）。一致すれば $x = im + j$ が解です。

どちらの列も長さは $m$ 程度なので、全体の手間は約 $2 N$ 回の掛け算と照合で済みます。 $g$ の位数が $N$ なので、解 $x$ は $N$ を法としてただ 1 つに決まります。 $i = 0, \dots, m - 1$ をすべて試しても一致しなければ、 $h$ は $g$ のべきで表せない（解なし）と判定できます。

手順

$g$ の位数 $N$ を確認し、 $m = ⌈ N ⌉$ とする（ $m^{2} \geq N$ となる最小の整数）。
ベビーステップ: $j = 0, 1, \dots, m - 1$ について $g^{j} mod p$ を、前の値に $g$ を掛けながら計算し、「値 → $j$ 」の表を作る（ $g^{0} = 1$ も必ず入れる）。
$c = g^{- m} mod p$ を求める。 $g^{m}$ を繰り返し二乗法で計算し、その逆元を拡張ユークリッドの互除法で求める（ $c \equiv g^{N - m}$ として計算してもよい）。
ジャイアントステップ: $γ_{0} = h$ 、 $γ_{i + 1} = γ_{i} c mod p$ として $i = 0, 1, \dots, m - 1$ の順に $γ_{i}$ を作り、そのつど表に同じ値があるか調べる。
$γ_{i} = g^{j}$ となる組 $(i, j)$ が見つかったら $x = im + j$ とし、 $g^{x} \equiv h (mod p)$ となることを確かめる。最後まで一致しなければ解はない。

例題

$5$ の法 $23$ での位数は $22$ である。 $5^{x} \equiv 21 (mod 23)$ を満たす整数 $x$ （ $0 \leq x < 22$ ）を、ベビーステップ・ジャイアントステップ法で求めよ。

例題の解答

手順1: $N = 22$ で、 $22 \approx 4.69$ より $m = ⌈ 22 ⌉ = 5$ とする。

手順2（ベビーステップ）: $5$ を掛けながら法 $23$ で計算すると、 $5^{0} = 1, 5^{1} = 5, 5^{2} = 25 \equiv 2, 5^{3} \equiv 10, 5^{4} \equiv 50 \equiv 4$ となる。表は ${1 \to 0, 5 \to 1, 2 \to 2, 10 \to 3, 4 \to 4}$ である。

手順3: $5 = (101)_{2}$ だから、 $5^{5} = 5^{4} \cdot 5^{1} \equiv 4 \cdot 5 = 20$ となる。逆元を求める。 $23 = 1 \cdot 20 + 3$ 、 $20 = 6 \cdot 3 + 2$ 、 $3 = 1 \cdot 2 + 1$ を逆にたどると $1 = 3 - 2 = 3 - (20 - 6 \cdot 3) = 7 \cdot 3 - 20 = 7 (23 - 20) - 20 = 7 \cdot 23 - 8 \cdot 20$ となる。よって $2 0^{- 1} \equiv - 8 \equiv 15$ で、 $c = 5^{- 5} \equiv 15 (mod 23)$ である（確認: $20 \cdot 15 = 300 = 13 \cdot 23 + 1$ ）。

手順4（ジャイアントステップ）: $γ_{0} = 21$ は表にない。 $γ_{1} = 21 \cdot 15 = 315 \equiv 16$ も表にない。 $γ_{2} = 16 \cdot 15 = 240 \equiv 10$ は表にあり、 $j = 3$ である。

手順5: $i = 2, j = 3$ より $x = 2 \cdot 5 + 3 = 13$ となる。確認する。 $5^{11} \equiv 5^{8} \cdot 5^{2} \cdot 5 = 16 \cdot 2 \cdot 5 = 160 \equiv - 1$ なので、 $5^{13} = 5^{11} \cdot 5^{2} \equiv - 2 \equiv 21 (mod 23)$ となり正しい。よって $x = 13$ 。

答え: $13$

よくある誤り

ジャイアントステップで $g^{- m}$ ではなく $g^{m}$ を掛けてしまう誤り。例題で $h \cdot (5^{5})^{i}$ と照合すると、一致から得られるのは $j \equiv x + im$ なので、 $x = im + j$ とすると誤る。正しくは $c = g^{- m}$ （例題では $15$ ）を掛けて $g^{j} \equiv h g^{- im}$ を照合し、 $x = im + j$ とする。
$m$ を $⌊ N ⌋$ にしてしまう誤り。 $N = 22$ で $m = 4$ とすると、表せる最大値は $im + j = 3 \cdot 4 + 3 = 15$ である。 $x = 16, \dots, 21$ が解のときに見つからない。正しくは $m = ⌈ N ⌉$ とし、 $m^{2} \geq N$ を満たすようにする（ $N = 22$ なら $m = 5$ ）。
$g^{- m}$ を「符号を反転した値」や分数と取り違える誤り。例えば $5^{5} \equiv 20$ から $5^{- 5} \equiv - 20 \equiv 3$ としてしまう。正しくは法 $23$ での逆元で、 $20 \cdot 15 \equiv 1$ より $5^{- 5} \equiv 15$ である。
ベビーステップの表に $g^{0} = 1$ （ $j = 0$ ）を入れ忘れる誤り。この場合、 $x$ が $m$ の倍数（例題なら $x = 5, 10, 15, 20$ ）のときに見落とす。正しくは $j = 0, 1, \dots, m - 1$ の $m$ 個すべてを表に入れる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

ベビーステップ・ジャイアントステップ法

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題