baby-step giant-step algorithm
$ a^x = b \mod m となる$ xを$ O(\sqrt{m})で求めるアルゴリズム。
$ r = \left\lceil \sqrt{m} \right\rceilとする。
$ x = ir + j, (0 \le i,j < r)とおくと
$ a^{ir+j} = b
$ a^j = b\left(a^{-r}\right)^i
と変形できるので、各$ iについて$ a^j = b\left(a^{-r}\right)^iとなる$ jが存在するか調べればよい。
存在判定は前計算で$ a^jの値を求めおき、hash table等に記録させれば十分高速に行える。
よって全体で$ O(\sqrt{m})で求められる。