メモ

yukicoderでゆるふわgolf

baby-step giant-step

この記事ではbaby-step giant-stepの「気持ち」を説明します。
アルゴリズムの説明のみであり、実装については一切説明していません。

○baby-step giant-step algorithmとは
巡回群上の離散対数問題を高速に解くアルゴリズム
平方分割でやる

○正確に
巡回群Gの台集合*1に全順序が定まる*2とする。
群の演算と順序の比較がO(1)でできるとする。
a,g\in Gが与えられたとき、a^x=gを満たす最小のx\in \mathbb{Z}_{\geq 0}O(\sqrt{|G|}\log|G|)で求めることができる。

アルゴリズム
N=|G|とおく。
最初に0\leq i < Kなるiに対してペア(i,a^i)を計算しておき、第二要素をキーにしてソートする。
ここで数yを決めたとき、★「a^{y+i}=gとなる0\leq i < Kがあるかどうか(あるなら最小のものを求める)」という問題を考える。
これは「a^i=ga^{-y}となる0\leq i < Kがあるかどうか」なので、最初に計算した配列上で二分探索することでO(\log K)で解くことができる。
yとして0,K,2K,\ldotsを順に考えることで、★の問題をO(N/K)回解くことにより元の問題に答えることができる。(もとの問題の答えはN未満なので)
全体でO(K\log K+(N/K)\log K)であるから、K=O(\sqrt{N})とすることでO(\sqrt{N} \log N)になる。

○例
\mathbb{F}_p^*上の離散対数問題
5^x=12 \mod 17を満たすxを求めよ
\mathbb{F}_{17}^*の元を\{1,\ldots,16\}\subset \mathbb{Z}と同一視して順序を定める。
0\leq i < 4について(i,5^i)を計算する
(0,1),(1,5),(2,8),(3,6)→ソート→(0,1),(1,5),(3,6),(2,8)
2^i=12*5^0となるものを探す→ない
2^i=12*5^{-4}=14となるものを探す→ない
2^i=12*5^{-8}=5となるものを探す→(1,5)が見つかる→答えは1+8=9

*1:Gの群構造を忘れて単なる集合だと思ったもの

*2:この条件は「Gは順序群である」とは異なる。ここでの順序は群構造と整合性がある必要はない