アルゴリズム論特論（塩田）第11回 (6) 今日のまとめ
前へ / 戻る
$\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}}}$
今日のまとめ
- 素数 $p$ を法としたとき、その乗法構造は「巡回群」と呼ばれ、「生成元」と呼ばれる元のべき乗が全ての既約剰余類を生成する。
- $\bmod\ p$ の既約剰余類 $y$ が生成元 $g$ の何乗になるかを $\log_g y$ と表して「離散対数」と呼ぶ。
- $\bmod\ p$ の離散対数は $\bmod\ p-1$ の数になる。
- $p$, $g$, $y$ を与えて $\log_g y$ を求める離散対数問題は困難な問題と考えられている。