アルゴリズム論特論(塩田)第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}}}$

今日のまとめ

  • 素数を法としたとき、その乗法構造は「巡回群」と呼ばれ、「生成元」と呼ばれる元のべき乗が全ての既約剰余類を生成する。
  • $\bmod\ p$ の既約剰余類 $y$ が生成元 $g$ の何乗になるかを $\log_g y$ と表して「離散対数」と呼ぶ。
  • $\bmod\ p$ の離散対数は $\bmod\ p-1$ の数になる。
  • $p$, $g$, $y$ を与えて $\log_g y$ を求める離散対数問題は困難な問題と考えられている。

自宅学習の例

  • サンプルプログラムを動かしてみる。