baby-step giant-step

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

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

○正確に
有限アーベル群G$G$の台集合*1に全順序が定まる*2とする。
群の演算と順序の比較がO(1)$O(1)$でできるとする。
a,g∈G$a,g\in G$が与えられたとき、ax=g$a^x=g$を満たす最小のx∈Z≥0$x\in {\mathbb{Z}}_{\ge 0}$をO(|G|−−−√log|G|)$O(\sqrt{|G|}\log |G|)$で求めることができる。

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

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

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

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