離散対数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

代数学における離散対数（りさんたいすう、discrete logarithm）とは、群論における対数の類似物である。離散対数を計算する問題は整数の因数分解(en:integer factorization)と以下の点が共通している：

両方とも難しい（量子コンピュータ以外では効率的に解くアルゴリズムが得られていない）
片方に対するアルゴリズムはしばしばもう片方にも利用できる
問題の困難性が暗号系の構築に利用されている

[編集] 例

離散対数の簡単な例は、素数 $p$ を法とする整数の乗法群 $\mathbb Z_p^\times$ で考えるとよい。これは1から $p - 1$ までの整数の集合であり、 $p$ を法とする乗算に対して群をなしている。

この群においてある元の $k$ 乗を知りたければ、普通の整数として $k$ 乗した後に $p$ で割ったときの剰余（余り）を取ればよい。例えば $\mathbb Z_{17}^\times$ を考える。この群において $34$ を求めるには、普通の整数として $34 = 81$ を計算し、 81を17で割って、余りの13を答えとする。なお3を掛ける毎に剰余を計算してもよい。

この逆操作が離散対数である。すなわち「 $3^k \equiv 13$ mod 17 のとき、この式を満たす $k$ はいくつか？」という問である。これには実際には無限個の解があるが（解に17の整数倍を足してよい不定性があるため）、普通はそのうちで最小の非負整数を選ぶ。すなわち $k = 4$ である。

[編集] 定義

一般に、 $G$ を位数 $n$ の巡回群とする（群の演算は積のように書き表す）。 $b$ を $G$ の生成元とする。このとき $G$ の任意の元 $g$ は、適当な整数 $k$ を用いて $g = b k$ の形に書ける。さらに同一の $g$ をそのように表現する任意の二つの整数は $n$ を法として合同である。よって、各 $g$ に $k$ の $n$ を法とする同値類を対応付けることで、次のような関数を定義できる：

$\log_b:\ G\ \rightarrow\ \mathbb Z_n$

ここで $\mathbb Z_n$ は整数環 $\mathbb Z$ の $n$ を法とした合同関係による商環である。この関数は群同型写像であり、底を $b$ としたときの離散対数と呼ぶ。

通常の対数と同様に底の変換公式が成立する：

$\log_c (g) = \log_c (b) \cdot \log_b (g)$

ここで $c$ は $G$ の別の生成元である。

[編集] アルゴリズム

群 $G$ における離散対数 $log b g$ を計算する効率の良いアルゴリズムは知られていない。ナイーブなアルゴリズムとしては、 $b$ の1乗、2乗、3乗、…を順に計算し、求める $g$ が得られるまで続ける方法がある。このアルゴリズムは $G$ の位数について線形な、すなわち要素の桁数（特に、何ビットか）について指数的な実行時間を要し、巨大な $G$ に対して実用的でない。

より高度なアルゴリズムも知られており、代表的なものを以下に挙げる。整数の因数分解アルゴリズムと同様のアイディアが多い。これらは上記のナイーブなアルゴリズムより高速であるものの、多項式時間では計算が終わらない。