Baby-step Giant-stepに関する説明です(簡単に書きます)。

Baby-step Giant-stepは \(f^{N}(x)=x\) となる( \(N\) 回繰り返すと元に戻る周期的な)関数 \(f\) があり、 \(s,g\) が与えられたときに \(f^{t}(s)=g\) となる最小の非負整数 \(t\) を求めるアルゴリズムです。

このアルゴリズムは、 \(f\) が以下の条件を満たす場合に使うことができます。

1. \(f(x)\) が高速に計算できる。
2. ある \(M\) に対して \(f^{M}(x)\) が高速に計算できる。
3. \(x\) が \(Y\subseteq X\)の要素であるか が高速に検索できる。
4. 逆関数 \(f^{-1}(x)\) が存在する(具体的に求める必要はない)。

たとえば、条件1,2,3が\(O(1)\)で求められる場合、 \(t=iM-j(1\leq i\leq \lceil N/M\rceil, 1\leq j\leq M)\) とすると

\[f^{iM-j}(s)=g\]

\[f^{j}(f^{iM-j}(s))=f^{j}(g)\]

\[f^{iM}(s)=f^{j}(g)\]

となり、 \(f^{j}(g)(1\leq j\leq M)\) を計算することで、 \(1\leq i\leq \lceil N/M\rceil\) を順に見て、 \(f^{iM}(s)\) と一致するような \(f^{j}(g)\) があれば \(t=iM-j\)が答えとなります。(条件4)

• \(f^{j}(g)(1\leq j\leq M)\) は \(O(M)\) で求められる。(条件1)
• \(f^{iM}(g)(1\leq i\leq \lceil N/M\rceil)\) は \(O(N/M)\) で求められる。(条件2)
• \(f^{iM}(s)\)と一致するような \(f^{j}(g)\)は\(O(1)\)で求められる。(条件3)

以上より、計算量は \(O(M+N/M)\) であり、 \(M=\sqrt{N}\)とすると、 \(O(\sqrt{N})\) となります。

アルゴリズムの直感的な説明として https://www.ioi-jp.org/camp/2017/2017-sp_camp-shiroshita1.pdf の図が分かりやすいです。

例題

• 例題1