勉強会に参加したい方は 概要 を確認してください。
弊社はエンジニアを熱烈募集しています． 以下から気軽にカジュアル面談申し込んでください． 就職・転職を考えている知人にも積極的に宣伝してください．
Spir | Smart scheduling calendar
この勉強会の宣伝もお願いします． 参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会 で実況や感想，質問を呟くなども．
<aside> ❓
剰余環 $\mathbb{Z}/k\mathbb{Z}$ 上の元 $x,y\in \mathbb{Z}/k\mathbb{Z}$ が与えられる。
$x^n = y$ を満たす自然数 $n$ が存在するか判定し、存在するならその最小値を求めよ。
</aside>
剰余環ではなく通常の整数環であれば、$x^n = y$ を満たす $n$ とはつまり対数 $\log_x y$ のこと。
通常の対数と異なり離散対数問題は難しく、おそらく多項式時間では解けない。 このことは後述する現代の暗号アルゴリズム Diffie-Hellman 鍵交換の安全性と関係している。
$x^1, x^2, x^3, \cdots$ と順番に $x$ の冪乗を計算する愚直なアルゴリズムでは $\Theta(k)$ 時間かかる。
この記事では離散対数問題をより一般化したうえで、 $O(\sqrt{k})$ 程度の時間で動くアルゴリズムを紹介する。
まず以下のような一般化が考えられる。
<aside> ❓
集合 $S$ の元 $x,y\in S$ と関数 $f:S\to S$ 、自然数 $N$ が与えられる。 ここで関数 $f$ の計算は $\Theta(T)$ 時間かかるとする。
$f^n(x) = y$ を満たす $N$ 以下の自然数 $n$ が存在するか判定し、存在するならその最小値を求めよ。
</aside>
ここまで一般化してしまうと $f$ の挙動に制限がなさすぎるため、愚直な $\Theta(NT)$ アルゴリズムしか存在しない。