指数(離散対数)の定義

指数(離散対数)の定義

 $p=7$ を法とするとき、$p-1=6$ の約数
 
\[\{\:1,\;2,\;3,\;4,\;5,\;6\:\}\]
のうち、$p-1=6$ 乗して初めて $1$ と合同になる数は $3$ と $5$ でした。つまり $7$ の原始根は $g=3,\;5$ です。そこで、たとえば原始根 $3$ のベキ乗をつくっていくと
 
\[\begin{align*}3^0\equiv 1&\quad (\mathrm{mod}\:7)\\[6pt]
3^1\equiv 3&\quad (\mathrm{mod}\:7)\\[6pt]
3^2\equiv 2&\quad (\mathrm{mod}\:7)\\[6pt]
3^3\equiv 6&\quad (\mathrm{mod}\:7)\\[6pt]
3^4\equiv 4&\quad (\mathrm{mod}\:7)\\[6pt]
3^5\equiv 5&\quad (\mathrm{mod}\:7)\end{align*}\]
のようになり、原始根をベキ乗して得られる数は $p-1=6$ 以下の数について全部出揃っています。すなわち
 
\[3^e\equiv a\quad (\mathrm{mod}\:7)\]
を満たす $a$ は $7$ の倍数を除いて必ず存在していることになります(たとえば $a=12$ は合同の意味で $a=5$ と同じです)。以前に学んだ 定理 E2 の前半部分によると

[定理 E2] $p$ を素数、$a$ を正整数とします。
 $(a,\;p)=1$ のとき、$e=\mathrm{ord}_p(a)$ とおくと
\[a^0\not\equiv a^1\not\equiv a^2\not\equiv \cdots\not\equiv a^{e-1}\quad (\mathrm{mod}\:p)\]

ですから、素数 $p$ の原始根の1つを $g$ としたとき、
 
\[g^e\equiv 1\quad (\mathrm{mod}\:p)\]
を満たす最小のベキ指数 $e$ が $p-1$ となるので、
 
\[\{\:g^0,\;g^1,\;g^2,\;\cdots,\;g^{p-2}\:\}\]
は互いに合同ではない $p-1$ 個の数であり、かついずれも $p-1$ で割り切れない数です。したがって、この集合の要素は
 
\[\{\:1,\;2,\;\cdots,\;p-1\:\}\]
のうちのいずれかの数と合同になり重複もありません。すなわち任意の正整数 $a$ について
 
\[g^e\equiv a\quad (\mathrm{mod}\:p)\]
を満たすような $e$ が
 
\[\{\:0,\;1,\;2,\;\cdots,\;p-2\:\}\]
の中に必ず存在します。そこで指数(離散対数)というものを次のように定義します。

[定義 E4] 素数 $p$ の原始根 $g$ と正整数 $a$ にたいして
\[g^e\equiv a\quad (\mathrm{mod}\:p)\]を満たすような整数 $e$ を $g$ を底とした $a$ の 指数(離散対数) と定義し、$e=\mathrm{Ind}_g(a)$ と書きます。

 記号 $\mathrm{Ind}$ は Index の略です。$a$ は離散真数とよばれます。
 $7$ の原始根 $3$ のべき乗を指数を使って書き直してみます。
 
\[\begin{align*}3^0\equiv 1&\quad (\mathrm{mod}\:7)\qquad\mathrm{Ind}_3(1)=0\\[6pt]
3^1\equiv 3&\quad (\mathrm{mod}\:7)\qquad\mathrm{Ind}_3(3)=1\\[6pt]
3^2\equiv 2&\quad (\mathrm{mod}\:7)\qquad\mathrm{Ind}_3(2)=2\\[6pt]
3^3\equiv 6&\quad (\mathrm{mod}\:7)\qquad\mathrm{Ind}_3(6)=3\\[6pt]
3^4\equiv 4&\quad (\mathrm{mod}\:7)\qquad\mathrm{Ind}_3(4)=4\\[6pt]
3^5\equiv 5&\quad (\mathrm{mod}\:7)\qquad\mathrm{Ind}_3(5)=5\end{align*}\]
 離散対数という名前の通り、$\mathrm{Ind}$ は対数の整数版なので、これから説明する計算法則の多くは実数の対数計算と一致します。

 $a=1$ のとき、$g^e\equiv 1$ を満たす $e$ は $0$ です。
 $a=g$ のとき、$g^e\equiv g$ を満たす $e$ は $1$ です。よって、

\[\mathrm{Ind}_g(1)=0,\quad\mathrm{Ind}_g(g)=1\]

となります。
 

指数(離散対数)の基本定理

 次回記事で指数(離散対数)に関する計算公式を導きますが、その前提となる基本定理を証明しておきます。

[定理 E7] $a\equiv b\:\:(\mathrm{mod}\:p)$ が成り立つとき、
\[\mathrm{Ind}_g(a)\equiv \mathrm{Ind}_g(b)\quad (\mathrm{mod}\:p-1)\]

[定理 E7 の証明] $\mathrm{Ind}_g(a)=x,\:\:\mathrm{Ind}_g(b)=y$ とおくと
 
\[a\equiv g^x,\quad b\equiv g^y\quad (\mathrm{mod}\:p-1)\]
 $a\equiv b\:\:(\mathrm{mod}\:p)$ ならば
 
\[g^x\equiv g^y\qquad\therefore g^{x-y}\equiv 1\quad (\mathrm{mod}\:p)\]
 一方、フェルマーの小定理より
 
\[g^{p-1}\equiv 1\quad (\mathrm{mod}\:p)\]
が成り立ちますが、$g$ は原始根なので $p-1\:|\:x-y$ , すなわち
 
\[x\equiv y\quad (\mathrm{mod}\:p-1)\]
となります。よって、
 
\[\mathrm{Ind}_g(a)\equiv \mathrm{Ind}_g(b)\quad (\mathrm{mod}\:p-1)\]
が成り立ちます。(証明終)

指数表(離散対数表)を作成します

 次回の指数計算の練習に備えて 指数表(離散対数表)を作っておきます。指数表とは数論版の対数表です。つまり
 
\[g^e\equiv a\;(\mathrm{mod}\:p)\quad\Longleftrightarrow\quad e=\mathrm{Ind}_g(a)\]
における離散真数 $a$ に対応する指数 $e$ を並べたものです。

 いつも $\mathrm{mod}\:7$ ばかりでは飽きるので、今回は $\mathrm{mod}\:11$ の原始根の中から $g=2$ を選びます。念のために $g=2$ が本当に原始根なのかを確認しおきます。べき乗していって $p-1=10$ で初めて $1$ と合同になれば原始根です。
 
\[\begin{align*}2^1&\equiv 2&\quad (\mathrm{mod}\:11)\\[6pt]
2^2&\equiv 4&\quad (\mathrm{mod}\:11)\\[6pt]
2^3&\equiv 8&\quad (\mathrm{mod}\:11)\\[6pt]
2^4&\equiv 5&\quad (\mathrm{mod}\:11)\\[6pt]
2^5&\equiv 10&\quad (\mathrm{mod}\:11)\\[6pt]
2^6&\equiv 9&\quad (\mathrm{mod}\:11)\\[6pt]
2^7&\equiv 7&\quad (\mathrm{mod}\:11)\\[6pt]
2^8&\equiv 3&\quad (\mathrm{mod}\:11)\\[6pt]
2^9&\equiv 6&\quad (\mathrm{mod}\:11)\\[6pt]
2^{10}&\equiv 1&\quad (\mathrm{mod}\:11)\\[6pt]\end{align*}\]
となるので、確かに $2$ は $11$ の原始根です。また、
 
\[2,\;4,\;8,\;5,\;10,\;9,\;7,\;3,\;6\]
は真数 $a$ ですから、これに $a=2^0=1$ も含めて、$a$ の小さい順に並べて指数表を作成すると次のようになります。

$a=g^e$ 1 2 3 4 5
$e$ 0 1 8 2 4
$a=g^e$ 6 7 8 9 10
$e$ 9 7 3 6 5

 表を参照して $e=\mathrm{Ind}_2(a)$ を求めることができます。たとえば
 
\[\mathrm{Ind}_2(4)=2,\quad\mathrm{Ind}_2(7)=7,\quad\mathrm{Ind}_2(9)=6\]
のようになります。 ≫ 指数計算の基本公式 ≫ 整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。