離散対数（Ind）

離散対数Ind

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

ですから、素数 $p$ の原始根の１つを $g$ としたとき、
$$g^e\equiv 1(\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(\mathrm{mod}p)$$
を満たすような $e$ が
$$\{0,1,2,\cdots ,p-2\}$$
の中に必ず存在します。そこで離散対数というものを次のように定義します。

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

$a=1$ のとき、$g^e\equiv 1$ を満たす $e$ は $0$ です。
$a=g$ のとき、$g^e\equiv g$ を満たす $e$ は $1$ です。よって、
$${\mathrm{Ind}}_g(1)=0,{\mathrm{Ind}}_g(g)=1$$
となります。

離散対数の基本定理を証明しておきます。

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

次は離散対数表を作っておきます。
離散対数表とは数論版の対数表です。つまり
$$g^e\equiv a(\mathrm{mod}p)⟺e={\mathrm{Ind}}_g(a)$$
における離散真数 $a$ に対応する離散対数 $e$ を並べたものです。

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

表を参照して $e={\mathrm{Ind}}_2(a)$ を求めることができます。たとえば

$${\mathrm{Ind}}_2(4)=2,{\mathrm{Ind}}_2(7)=7,{\mathrm{Ind}}_2(9)=6$$
のようになります。

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

[証明]
(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 ab(\mathrm{mod}p)$$
と表せるので
$$g^z\equiv ab\equiv g^x{g}^y\equiv g^{x+y}(\mathrm{mod}p)$$
すなわち
$$g^z\equiv g^{x+y}(\mathrm{mod}p)$$
定理 E7

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

(2) (1) の公式を繰り返し用いると
$${\mathrm{Ind}}_g(abc\cdots )={\mathrm{Ind}}_g(a)+{\mathrm{Ind}}_g(b)+{\mathrm{Ind}}_g(c)+\cdots (\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)(\mathrm{mod}p-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 ab(\mathrm{mod}p)$$
と表せるので
$$(g^y{)}^z\equiv b^z\equiv a(\mathrm{mod}p)$$
すなわち
$$g^{yz}\equiv g^x(\mathrm{mod}p)$$
定理 E7 より
$$yz\equiv x(\mathrm{mod}p)$$
したがって
$${\mathrm{Ind}}_b(a){\mathrm{Ind}}_g(b)={\mathrm{Ind}}_g(a)(\mathrm{mod}p-1)$$
が成り立ちます。（証明終）

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

まずは公式 (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(\mathrm{mod}10)$$
と計算できます（法が１つ下がることに注意！）。実際、左辺を離散対数表で確認してみると
$${\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(\mathrm{mod}10)$$
となります。左辺を離散対数表で確認してみると
$${\mathrm{Ind}}_2(49)={\mathrm{Ind}}_2(5)=4$$
となって、確かに公式は正しいことがわかります。次に公式 (3) を確認するために、原始根 $g=6$ の離散対数表を用意します。

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

ベキ乗合同計算への応用

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

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

一次合同方程式への応用

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

${\mathrm{Ind}}_2(5)=4,{\mathrm{Ind}}_2(7)=7$ なので
$$4+{\mathrm{Ind}}_2(x)\equiv 7(\mathrm{mod}10)$$
となります。両辺から $4$ を引いて
$${\mathrm{Ind}}_2(x)\equiv 3(\mathrm{mod}10)$$
また表から離散対数が $3$ となる真数を探すと $e=8$ なので
$$x\equiv 8(\mathrm{mod}11)$$
となります。検算してみると
$$5\times 8\equiv 40\equiv 7(\mathrm{mod}11)$$
となって、確かに合同方程式を満たしています。