Baby Step Giant Step Algorithm

個人的メモ

離散対数問題は $a^x = b\ (\mathrm{mod} \ p)$ で $a, b, p$ が与えられている状況で $x$ を求める問題で一般的には解くのは難しいとされ Elgamal 暗号とか Diffie-Hellman 鍵共有の安全性を担保しているものである. しかし, 離散対数問題は量子コンピュータを用いた Shor のアルゴリズムで効率的に解けると言われており, それに代わる耐量子性を持つ暗号方式が現在複数提案されている.
アルゴリズムについてはそこまで難しくないので別のサイトを参考にしてください.

(補足)
yosupo さんの library-checker で $\mathrm{gcd}(a, p)$ が $1$ とは限らない場合についての問題が出されていたので考えてみた. ちなみに $\mathrm{gcd}(a, p) \neq 1$ だと逆元が取れず, アルゴリズムが回らないので $\mathrm{gcd}(a, p) = 1$ に変形する必要があることに注意.
まず $g = \mathrm{gcd}(a, p)$ をとり, $a = cg$, $p = dg$ とする. このとき $b \% g \neq 0$ なら解は存在しないので $b = eg$ が成り立つとする. すると $c^x g^{x-1} = e\ (\mathrm{mod} \ d) \Leftrightarrow a^{x-1} = c^{-1} e\ (\mathrm{mod}\ d)$ のように同値変形できる. baby_step_giant_step 関数は最小の非負整数 $x$ を返すので例外として元の問題において $x = 0$ が解となるかどうかを確認しておく.
$\mathrm{gcd}(a, d) \neq 1$ ならまた同様の操作を繰り返す. この操作によって $mod$ が半分以下になり高々 $\mathrm{ceil}(\log p)$ 回で終わるので問題ない.
$\O (1)$ で変形できる方法があるのか分からないが, 悪くない方法な気はしている.