BabyStep GiantStep法(BSGS法)

DLP問題を解くアルゴリズムの一つとしてBabyStep GiantStep法があります。

www.pebblewind.com

DLP問題とは、対称群の位数nに対して、生成元をg、群のある元をaとして、
${g}^{x} = a$ を満たすxを求める問題です。
ここで、解はただ一つのみ必ず存在することは前提とします。
なので、解が存在するかどうかを調べる必要はありません。
問題はどうやって計算量を少なく求めるかです。

xは{0, 1, 2, ..., n-1}のいずれかです。
xをある数の倍数に小さい数を加えたものとして計算できれば、少ない計算量で求めることができるんじゃね？
ってのがこのアルゴリズムのアイデアです。

まずある数の倍数として適当な値とはどのくらいの大きさかを考えます。
$x = qm + r$ と表した時、xは最大でn-1なのですから、
mはnの平方根くらいの大きさなら、qとrを小さい方から闇雲に設定した時、xは0からn-1の全てを
最も効率よく網羅できそうですね。
そこでmはnの平方根を整数に切り上げたものに取ることにします。
そしてxをmで割った商をq, 余りをrとします。

${g}^{qm + r} = a$ を変形して、
${{g}^{m}}^q = a {g}^{-r}$ とします。
この右辺の値を全ての余りのケースについて計算しておきます。
つまり、 $a {g}^{0}, a {g}^{-1}, a {g}^{-2}, ..., a {g}^{-m+1}$ を計算しておきます。
これをベビーステップ集合と言います。

次に左辺をqの小さい方から順番に計算していき、ベビーステップ集合内の値と一致するまで繰り返します。
手順として $d = {g}^{m}$ をまず計算し、 ${d}^{1}, {d}^{2}, {d}^{3}, ...$ のように計算していきます。
これをジャイアントステップ集合と言います。
一致するものが見つかった場合は、
${d}^{q} = a {g}^{-r}$ となり、qとrが確定したということですから、
${g}^{mq} {g}^{r} = a$ となるので、x = mq + r と求まります。

大事なのは計算量です。
少なくとも、ベビーステップ集合の計算で、 $m = \sqrt n$ 回のかけ算が必ず必要となります。
したがって、このアルゴリズムのオーダーは $\sqrt n$ となり、 $n > {2}^{160}$ 程度あれば、
ハイパーコンピューターをもってしても解くことは不可能となります。