Baby-Step Giant-Step
BSGS アルゴリズムは離散対数 x=im+j（m=ceil(√n)）を 2 段階に分解する。まず g^j を計算して表に登録し（ベビーステップ）、次に h*(g^(-m))^i を探索する（ジャイアントステップ）。
目的
時間と空間のトレードオフにより、O(√n) の計算量で離散対数問題を解く。
メカニズム
m=ceil(√n) とする。ベビーステップでは {g^j : 0≤j<m} を計算して保存する。ジャイアントステップでは i=0,1,… について h*g^(-im) を計算して表を照合し、一致すれば x=im+j となる。計算時間 O(√n)、空間 O(√n) である。
ユースケース
- 離散対数（DLP）の求解
- クリプトアナリシス（暗号解析）
- 数論アルゴリズム