アルゴリズム論特論（塩田）第11回 (5) 離散対数問題
前へ / 戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
離散対数問題
Def.14 素数 $p$, $\bmod\ p$ の生成元 $g$, $y \in \znzc{p}$ を与えたとき
$\log_g\, y$ を求める問題を離散対数問題 ( DLP = Discrete Logarithm Problem ) と呼ぶ。
Th.15 単純検索による $\bmod\ p$ の離散対数問題の計算量は $O(p\log^2 p)$.
計算量に $p$ が掛かっていますので暗号に使うビット数では天文学的時間がかかります。
証明 $g^1$, $g^2$, $\cdots$ が $y$ に一致するまで、
$($ $\times g) \,\%\, p$
という計算を、平均で $p/2$ 回繰り返さなければならないので。(証明終)
離散対数問題は一般に困難な問題と考えられていて、このことを利用した暗号技術を次回勉強します。
参考
- 暗号ライブラリ crypto.py ... 以下のプログラムに引用
- 単純検索による離散対数計算 DLP.py
... $p$ が 25ビットあたりから実行時間が急激に増えていくはずです。