アルゴリズム論特論（塩田）第11回 (4)　離散対数
前へ / 戻る / 次へ $\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}}}$

離散対数

　指数関数 $y=a^x$ の逆関数を対数関数と呼ぶことの analogy で、 $y \equiv g^x \pmod{p}$ の逆関数を考えます。
Def.8　$g$ を $\bmod\ p$ の生成元とするとき、 Th.7 よりすべての $y \in \znzc{p}$ に対して
$y = g^x$
を満たす指数 $x$ が存在する。この $x$ を
$x = \log_g y$
と表し「 $\bmod\ p$ における、底 $g$ に対する $y$ の離散対数」と呼ぶ。
Ex.9　 $p=11$, $g=2$ のとき
  • $\log_2 3 =$ ？
  • $\log_2 5 =$ ？
  • $\log_2 7 =$ ？
$p=13$, $g=2$ のとき
  • $\log_2 3 =$ ？
  • $\log_2 5 =$ ？
  • $\log_2 7 =$ ？
答え
　実数と違って法演算の数には大きさの概念がないので、 離散対数の値は全く予測のつかないものとなっています。

$\bmod p$ の離散対数は $\bmod (p-1)$ の数

　離散対数は $0 \leqq \log_g y \lt p-1$ の範囲で必ずひとつ見つかりますが、 $g^{p-1}=1$ なので実は自由度があります。
Th.10　$\log_g y$ は $\bmod\ p-1$ で確定する。
証明　$y = g^x = g^{x'}$ となるための $x$, $x'$ の必要十分条件は何か、を考える。
$g^x = g^{x'}$ $\Leftrightarrow$ $g^{x-x'}=1$
 $\Leftrightarrow$ $x-x'$ は $g$ の位数の倍数 ( Th.3 )
 $\Leftrightarrow$ $x-x'$ は $p-1$ の倍数 ( Th.7 )
 $\Leftrightarrow$ $x \equiv x' \pmod{(p-1)}$
(証明終)

　この定理により、対数法則は $\bmod$ 付きで成立することがわかります。
Th.11（対数法則）　$\log_g(yz) \equiv \log_g y + \log_g z \pmod{(p-1)}$.
証明　$y = g^x$, $z = g^{x'}$ とすると $yz = g^{x+x'}$ ゆえ、Th.10 より
$\log_g(yz) \equiv x + x' \equiv \log_g y + \log_g z \pmod{(p-1)}$.
(証明終)
Ex.12　$p=13$, $g=2$, $y=5$, $z=7$ のとき、
$\log_g(yz) = \log_2 35 = \log_2 9 = 8$,
$\log_g y + \log_g z = \log_2 5 + \log_2 7 = 11 + 9 = 20$.
$8$ と $20$ では食い違って見えますが $\bmod\ 12$ で一致しています。
Rem.13　実数の対数も、定義域は全ての正数の集合、値域は全ての実数の集合で、定義域と値域は別ものでした。 離散対数はそのずれが微妙で、定義域は $\bmod\ p$, 値域は $\bmod\ p-1$ という訳です。

前へ / 戻る / 次へ