離散対数 (Ind) の定義

離散対数の定義

 $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\]
のようになります。
 

離散対数計算の基本公式

 離散対数計算の基本公式です。

[定理 E8] $p$ を奇素数、$g$ を $p$ の原始根の1つ、$n$ を正整数とすると、
\[\begin{align*}&\mathrm{Ind}_g(ab)\equiv\mathrm{Ind}_g(a)+\mathrm{Ind}_g(b)&\quad (\mathrm{mod}\:p-1)&\qquad(1)\\[6pt]
&\mathrm{Ind}_g(a^n)\equiv n\mathrm{Ind}_g(a)&\quad (\mathrm{mod}\:p-1)&\qquad(2)\end{align*}\]

[定理 E8 の証明]
(1) $\mathrm{Ind}_g(a)=x,\:\:\mathrm{Ind}_g(b)=y,\:\:\mathrm{Ind}_g(ab)=z$ とおくと、
 
\[g^x\equiv a,\:\:g^y\equiv b,\:\:g^z\equiv a\,b\quad (\mathrm{mod}\:p)\]
と表せるので
 
\[g^z\equiv a\,b\equiv g^x\,g^y\equiv g^{x+y}\quad (\mathrm{mod}\:p)\]
 すなわち
 
\[g^z\equiv g^{x+y}\quad (\mathrm{mod}\:p)\]
 前回記事の 定理 E7

  $a\equiv b\:\:(\mathrm{mod}\:p)\quad\Longrightarrow\quad\mathrm{Ind}_g(a)\equiv \mathrm{Ind}_g(b)\;(\mathrm{mod}\:p-1)$

より、法を1つ下げて
\[z\equiv x+y\quad (\mathrm{mod}\:p-1)\]
 すなわち
 
\[\mathrm{Ind}_g(ab)\equiv\mathrm{Ind}_g(a)+\mathrm{Ind}_g(b)\quad (\mathrm{mod}\:p-1)\]
が成り立ちます。

(2) (1) の公式を繰り返し用いると
 
\[\mathrm{Ind}_g(abc\cdots)=\mathrm{Ind}_g(a)+\mathrm{Ind}_g(b)+\mathrm{Ind}_g(c)+\cdots\quad (\mathrm{mod}\:p-1)\]
となるので、
 
\[\mathrm{Ind}_g(a^n)\equiv\mathrm{Ind}_g(a)+\mathrm{Ind}_g(a)+\mathrm{Ind}_g(a)+\cdots=n\mathrm{Ind}_g(a)\quad (\mathrm{mod}\:p-1)\]
が得られます。(証明終)

 次の定理は離散対数の底の変換公式です。

[定理 E9] $p$ を奇素数、$g$ を $p$ の原始根の1つとすると
\[\mathrm{Ind}_b(a)\mathrm{Ind}_g(b)=\mathrm{Ind}_g(a)\quad (\mathrm{mod}\:p-1)\qquad(3)\]

[定理 E9 の証明] $\mathrm{Ind}_g(a)=x,\:\:\mathrm{Ind}_g(b)=y,\:\:\mathrm{Ind}_g(ab)=z$ とおくと、
 
\[g^x\equiv a,\:\:g^y\equiv b,\:\:g^z\equiv a\,b\quad (\mathrm{mod}\:p)\]
と表せるので
 
\[(g^y)^z\equiv b^z\equiv a\quad (\mathrm{mod}\:p)\]
 すなわち
 
\[g^{yz}\equiv g^x\quad (\mathrm{mod}\:p)\]
 定理 E7 より
 
\[yz\equiv x\quad (\mathrm{mod}\:p)\]
 したがって
 
\[\mathrm{Ind}_b(a)\mathrm{Ind}_g(b)=\mathrm{Ind}_g(a)\quad (\mathrm{mod}\:p-1)\]
が成り立ちます。(証明終)
 

離散対数計算の具体例

 離散対数の公式が出揃ったところで具体例で練習してみましょう。
 $11$ の原始根 $2$ の離散対数表を再掲します。

$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

 まずは公式 (1) を確認してみます。
 たとえば $\mathrm{Ind}_2(3)=8,\;\mathrm{Ind}_2(5)=4$ なので、
 
\[\mathrm{Ind}_2(15)\equiv \mathrm{Ind}_2(3)+\mathrm{Ind}_2(5)=12\equiv 2\quad (\mathrm{mod}\:10)\]
と計算できます(法が1つ下がることに注意!)。実際、左辺を離散対数表で確認してみると
 
\[\mathrm{Ind}_2(15)=\mathrm{Ind}_2(4)=2\]
となっています(真数は法 $11$ で合同計算します)。次は公式 (2) です。たとえば
 
\[\mathrm{Ind}_2(7^2)\equiv 2\,\mathrm{Ind}_2(7)=2\times 7=14\equiv 4\quad (\mathrm{mod}\:10)\]
となります。左辺を離散対数表で確認してみると
 
\[\mathrm{Ind}_2(49)=\mathrm{Ind}_2(5)=4\]
となって、確かに公式は正しいことがわかります。次に公式 (3) を確認するために、原始根 $g=6$ の離散対数表を用意します。

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

 公式 (3) によると、たとえば
 
\[\mathrm{Ind}_2(6)\,\mathrm{Ind}_6(5)\equiv\mathrm{Ind}_2(5)=4\quad (\mathrm{mod}\:10)\]
というように計算できます。左辺を離散対数表で確認してみると
 
\[\mathrm{Ind}_2(6)\,\mathrm{Ind}_6(5)=9\times 6=54\equiv 4\quad (\mathrm{mod}\:10)\]
となっています。
 

ベキ乗計算への応用

 次のようなベキ乗の合同計算を公式を使って計算してみます。
 
\[x\equiv 3^7\quad (\mathrm{mod}\:11)\]
 両辺の離散対数をとると公式 (2) より
 
\[\mathrm{Ind}_2(x)\equiv 7\,\mathrm{Ind}_2(3)\quad (\mathrm{mod}\:10)\]
 ここで原始根 $g=2$ の離散対数表を再掲します。

$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

 表から $\mathrm{Ind}_2(3)=8$ なので
 
\[\mathrm{Ind}_2(x)\equiv 7\times 8\equiv 56\equiv 6\quad (\mathrm{mod}\:10)\]
 表から離散対数が $6$ となる真数を探すと $e=9$ なので
 
\[x\equiv 6\quad (\mathrm{mod}\:11)\]
という答えが得られます。念のために検算すると
 
\[3^7=2187=198\times 11+9\]
となって、確かに $11$ で割ると余りは $9$ です。離散対数をとったり、また戻したりとする過程で法が下がったり上がったりすることに注意してください。
 

1次合同方程式への応用

 次は離散対数を使って次のような合同方程式
 
\[5x\equiv 7\quad (\mathrm{mod}\:11)\]
を解いてみます。両辺の離散対数をとると
 
\[\mathrm{Ind}_2(5)+\mathrm{Ind}_2(x)\equiv \mathrm{Ind}_2(7)\quad (\mathrm{mod}\:10)\]
 $11$ の原始根 $g=2$ の離散対数表を調べます。

$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

 $\mathrm{Ind}_2(5)=4,\:\:\mathrm{Ind}_2(7)=7$ なので
 
\[4+\mathrm{Ind}_2(x)\equiv 7\quad (\mathrm{mod}\:10)\]
となります。両辺から $4$ を引いて
 
\[\mathrm{Ind}_2(x)\equiv 3\quad (\mathrm{mod}\:10)\]
 また表から離散対数が $3$ となる真数を探すと $e=8$ なので
 
\[x\equiv 8\quad (\mathrm{mod}\:11)\]
となります。検算してみると
 
\[5\times 8\equiv 40\equiv 7\quad (\mathrm{mod}\:11)\]
となって、確かに合同方程式を満たしています。 ≫ ラグランジュの定理 ≫ 整数論入門講座


 

コメントをどうぞ

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