アルゴリズム論特論（塩田）第12回 (1) 離散対数の復習
戻る / 次へ
$\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$ が素数ならば $\znzc{p}$ は巡回群である。
すなわち、生成元と呼ばれる元 $g \in \znzc{p}$ が存在して、
$g$ のべき乗で $\znzc{p}$ の全ての要素が作れる
$\langle\, g \,\rangle =\{\,g^0, g^1, g^2, \cdots\,\}=\znzc{p}.$
- $y \in \znzc{p}$ に対し、
$g^x = y$
を満たすべき指数 $x$ を $x = \log_g y$ と表し、
$\bmod\ p$ での底 $g$ に対する $y$ の離散対数と呼ぶ。
-
$x = \log_g y$ は $\bmod\ (p-1)$ の数である。