指数(離散対数)計算の基本公式

指数(離散対数)計算の基本公式

 指数計算の基本公式です。

[定理 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)\]
となって、確かに合同方程式を満たしています。

 ≫ ラグランジュの定理 ≫ 整数論入門講座

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

コメントをどうぞ

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